Triangulating and guarding realistic polygons

DOI10.1016/J.COMGEO.2013.03.005MaRDI QIDQ390140zbMATH OpenOpenAlexWikidataFDO

Authors Greg Aloupis, Prosenjit Bose, Vida Dujmović, Chris Gray, Stefan Langerman, Bettina Speckmann

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2013.03.005

zbMATH Keywords

art gallerygeometric algorithmguardingpolygontriangulationvisibility-polygon computation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Realistic input models place certain restrictions on the shape of objects fed to geometric algorithms. In this way unusual worst-case examples are excluded and complexity bounds might mimic the observed behavior of an algorithm more accurately.NEWLINENEWLINEThe authors propose \(k\)-guardable objects as a new model of realistic input. They remark that \(\varepsilon\)-good polygons are \(k\)-guardable and show that their notion generalizes the notion of \((\alpha,\beta)\)-covered polygons (Theorem 1). Furthermore, they present two algorithms to triangulate a \(k\)-guardable polygon. The first algorithm is based on an involved subroutine, but does not need the guards as an input. The second algorithm uses visibility-polygon computations and requires the guards as an input. Both algorithms take linear time under the assumption that the number of guards is constant (Theorem 2, Theorem 3).

Recommendations

• Guarding scenes against invasive hypercubes.
• \(K\)-vertex guarding simple polygons
• Generalized guarding and partitioning for rectilinear polygons
• Note on the paper ``K-vertex guarding simple polygons
• Approximate guarding of monotone and rectilinear polygons

Cited in

(6)

• Guarding scenes against invasive hypercubes.
• Guarding disjoint triangles and claws in the plane
• Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
• On k-convex polygons
• Robustly guarding polygons
• A note on the perimeter of fat objects

This page was built for publication: Triangulating and guarding realistic polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390140)