Document Open Access Logo

Constrained Geodesic Centers of a Simple Polygon

Authors Eunjin Oh, Wanbin Son, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.29.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Eunjin Oh
Wanbin Son
Hee-Kap Ahn

Cite As Get BibTex

Eunjin Oh, Wanbin Son, and Hee-Kap Ahn. Constrained Geodesic Centers of a Simple Polygon. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.29

Abstract

For any two points in a simple polygon P, the geodesic distance between them is the length of the shortest path contained in P that connects them. A geodesic center of a set S of sites (points) with respect to P is a point in P that minimizes the geodesic distance to its farthest site. In many realistic facility location problems, however, the facilities are constrained  to lie in feasible regions. In this paper, we show how to compute the geodesic centers constrained to a set of line segments or simple polygonal regions contained in P. Our results provide substantial improvements  over previous algorithms.

Subject Classification

Keywords
  • Geodesic distance
  • simple polygons
  • constrained center
  • facility location
  • farthest-point Voronoi diagram

Metrics

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

References

  1. Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman, and Eunjin Oh. A linear-time algorithm for the geodesic center of a simple polygon. In Proc. 31st Int'l Symposium on Computational Geometry (SoCG 2015), pages 209-223, 2015. Google Scholar
  2. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete &Computational Geometry, 9(1):217-255, 1993. Google Scholar
  3. Tetsuo Asano and Godfried Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, 1985. Google Scholar
  4. Luis Barba. Disk constrained 1-center queries. In Proc. 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 15-19, 2012. Google Scholar
  5. Luis Barba, Prosenjit Bose, and Stefan Langerman. Optimal algorithms for constrained 1-center problems. In Proc. 11th Latin American Theoretical Informatics Symposium (LATIN 2014), pages 84-95, 2014. Google Scholar
  6. Prosenjit Bose, Stefan Langerman, and Sasanka Roy. Smallest enclosing circle centered on a query line segment. In Proc. 20th Canadian Conference on Computational Geometry (CCCG 2008), pages 167-170, 2008. Google Scholar
  7. Prosenjit Bose and Godfried Toussaint. Computing the constrained Euclidean geodesic and link center of a simple polygon with applications. In Proc. 14th Computer Graphics International (CGI 1996), pages 102-110, 1996. Google Scholar
  8. Prosenjit Bose and Qingda Wang. Facility location constrained to a polygonal domain. In Proc. 5th Latin American Theoretical Informatics Symp. (LATIN'02), pages 153-164, 2002. Google Scholar
  9. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete &Computational Geometry, 6(3):485-524, 1991. Google Scholar
  10. 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
  11. Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing, 22(6):1286-1302, 1993. Google Scholar
  12. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1):209-233, 1987. Google Scholar
  13. Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. Google Scholar
  14. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  15. Ferran Hurtado, Vera Sacristán, and Godfried Toussaint. Some constrained minimax and maximin location problems. Studies in Locational Analysis, 15:17-35, 2000. Google Scholar
  16. David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, 1983. Google Scholar
  17. D.T. Lee and V.B. Wu. Multiplicative weighted farthest neighbor Voronoi diagrams in the plane. In Proc. International Workshop on Discrete Mathematics and Algorithms, pages 154-168, 1993. Google Scholar
  18. Nimrod Megiddo. Linear-time algorithms for linear programming in ℝ³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  19. Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. To appear in Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), 2016. Google Scholar
  20. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete &Computational Geometry, 4(6):611-626, 1989. 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