Document Open Access Logo

Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

Authors Eunjin Oh, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.51.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Eunjin Oh
Hee-Kap Ahn

Cite As Get BibTex

Eunjin Oh and Hee-Kap Ahn. Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.51

Abstract

We consider the geodesic convex hulls of points in a simple polygonal region in the presence of non-crossing line segments (barriers) that subdivide the region into simply connected faces. We present an algorithm together with data structures for maintaining the geodesic convex hull of points in each face in a sublinear update time under the fully-dynamic setting where both input points and barriers change by insertions and deletions. The algorithm processes a mixed update sequence of insertions and deletions of points and barriers. Each update takes O(n^2/3 log^2 n) time with high probability, where n is the total number of the points and barriers at the moment. Our data structures support basic queries on the geodesic convex hull, each of which takes O(polylog n) time. In addition, we present an algorithm together with data structures for geodesic triangle counting queries under the fully-dynamic setting. With high probability, each update takes O(n^2/3 log n) time, and each query takes O(n^2/3 log n) time.

Subject Classification

Keywords
  • Dynamic geodesic convex hull
  • dynamic simple polygons

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, and Li Zhang. Kinetic collision detection between two simple polygons. Computational Geometry, 27(3):211-235, 2004. Google Scholar
  2. Jon Louis Bentley and James B. Saxe. Decomposable searching problems 1: Static-to-dynamic transformations. Journal of Algorithms, 1(4):297-396, 1980. Google Scholar
  3. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 617-626, 2002. Google Scholar
  4. Timothy M. Chan. Optimal partition trees. Discrete & Computational Geometry, 47(4):661-690, 2012. Google Scholar
  5. Timothy M. Chan and Yakov Nekrich. Towards an optimal method for dynamic planar point location. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 390-409, 2015. Google Scholar
  6. Bernard Chazelle. Lower bounds on the complexity of polytope range searching. Journal of the American Mathematical Society, 2(4):637-666, 1989. Google Scholar
  7. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1):54-68, 1994. Google Scholar
  8. Bernard Chazelle, Micha Sharir, and Emo Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica, 8(1):407-429, 1992. Google Scholar
  9. Yi-Jen Chiang, Franco P. Preparata, and Roberto Tamassia. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM Journal on Computing, 25(1):207-233, 1996. Google Scholar
  10. Anurag Ganguli, Jorge Cortés, and Francesco Bullo. Multirobot rendezvous with visibility sensors in nonconvex environments. IEEE Transactions on Robotics, 25(2):340-352, 2009. Google Scholar
  11. Michael T. Goodrich and Roberto Tamassia. Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations. Journal of Algorithms, 23(1):51-73, 1997. Google Scholar
  12. Mashhood Ishaque and Csaba D. Tóth. Relative convex hulls in semi-dynamic arrangements. Algorithmica, 68(2):448-482, 2014. Google Scholar
  13. David Kirkpatrick and Jack Snoeyink. Computing common tangents without a separating line. In Proceedings of the 4th International Workshop on Algorithms and Data Structures (WADS 1995), pages 183-193, 1995. Google Scholar
  14. Jiří Matousěk. Efficient partition trees. Discrete &Computational Geometry, 8(3):315-334, 1992. Google Scholar
  15. Jiří Matousěk. Lectures on discrete geometry. Springer Science & Business Media, 2013. Google Scholar
  16. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Science, 23(2):166-204, 1981. Google Scholar
  17. Mark H. Overmars and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problem. Information Processing Letters, 12(4):168-173, 1981. Google Scholar
  18. Jack Sklansky, Robert L. Chazin, and Bruce J. Hansen. Minimum-perimeter polygons of digitized silhouettes. IEEE Transactions on Computers, C-21(3):260-268, 1972. Google Scholar
  19. Ileana Streinu. Pseudo-triangulations, rigidity and motion planning. Discrete and Computational Geometry, 34:587-635, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact