Barrier resilience of visibility polygons

By: 
Zahra Momtazian
Date and Time: 
2016-09-17 12:30
Place: 
628 room
Abstract: 

 In barrier resilience problems, we are given a set of barriers and two points $s$ and $t$. The task is to find the minimum number of barriers one has to remove such that there is a path between $s$ and $t$ that does not cross a barrier. The barrier resilience of arrangements of geometric objects such as circles and line segments have been considered. We will consider the problem of computing the barrier resilience of a set of visibility polygons inside a polygon. In simple polygons the problem is solvable in time linear in the number of edges. In polygons with holes the problem is APX-hard, but for special cases there are polynomial time algorithms. 

Biography: 

Zahra Momtazian is a MSc student at Sharif university under the supervision of Prof. Ghodsi. Her research interests lie in Computational Geometry.

Join our Google Group Now!



GET IN TOUCH WITH US

Contact us

Sharif University of Technology, Department of Computer Engineering

Room 712, CE Algorithms Lab
P.O. Box 11155-9517, Tehran, Iran

Tel: +9821-6600-6675

Education - This is a contributing Drupal Theme
Design by WeebPal.