6533b859fe1ef96bd12b7f71

RESEARCH PRODUCT

Optimal Guard Placement Problem Under L-Visibility

Sandip DasDebabrata BardhanSasanka Roy

subject

Art gallery problemPolygon coveringComputer Science::Computational GeometryConvex polygonCombinatoricsMonotone polygonBiggest little polygonTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYStar-shaped polygonVisibility polygonSimple polygonComputingMethodologies_COMPUTERGRAPHICSMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

Two points a and b in the presence of polygonal obstacles are L-visible if the length of the shortest path avoiding obstacles is no more than L. For a given convex polygon Q, Gewali et al [4]. addressed the guard placement problem on the exterior boundary that will cover the maximum area exterior to the polygon under L-visibility. They proposed a linear time algorithm for some given value of L. When the length L is greater than half of the perimeter, they declared that problem as open. Here we address that open problem and present an algorithm whose time complexity is linear in number of vertices of the polygon.

yearjournalcountryeditionlanguage
2006-01-01
https://doi.org/10.1007/11751540_2