Geodesic Center of a Simple Polygon using a Logarithmic Number of Extra Variables

• Autorzy: Kavand P. , Mohades A.

Identyfikatory

DOI

10.3233/FI-2019-1844

• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n) words of O(log n) bits for reading and writing. The algorithm runs in O(n⁴) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthestsite Voronoi diagram of the corners of the polygon can be computed in the same time and space. As a sub-result, we present an s-workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O(n²/s) expected time where s∈Ω(log n)∩O([formula]).

Słowa kluczowe

EN

computational geometry; memory-constrained algorithms; geodesic center; geodesic farthest neighbor; geodesic farthest-site Voronoi diagram

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 3
• Strony: 211--235
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Kavand P.

• Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

autor

Mohades A.

• Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Bibliografia

• [1] Asano T, Buchin K, Buchin M, Korman M, Mulzer W, Rote G, Schulz A. Memory-constrained algorithms for simple polygons. Computational Geometry, 2013. 46(8):959-969. URL https://doi.org/10.1016/j.comgeo.2013.04.005.
• [2] Har-Peled S. Shortest path in a polygon using sublinear space. Journal of Computational Geometry, 2016. 7(2):19-45.
• [3] Aronov B, Korman M, Pratt S, van Renssen A, Roeloffzen M. Time-Space Trade-offs for Triangulating a Simple Polygon. In: 2016 SWAT 15th Scandinavian Symposium and Workshops on Algorithm Theory, Reykjavik, Iceland, 22-24 June 2016, 30. 2016 pp. 1-12. doi:10.4230/LIPIcs.SWAT.2016.30.
• [4] Barba L, Korman M, Langerman S, Silveira RI. Computing a visibility polygon using few variables. Computational geometry, 2014. 47(9):918-926. URL https://doi.org/10.1016/j.comgeo.2014.04.001.
• [5] Banyassady B, Korman M, Mulzer W. Computational Geometry Column 67. SIGACT News, 2018. 49(2):77-94. doi:10.1145/3232679.3232692.
• [6] Chazelle B. A theorem on polygon cutting with applications. In: 1982 SFCS 23rd Annual Symposium on Foundations of Computer Science, Chicago, IL, USA, USA, 3-5 November 1982. IEEE Xplore, 1982 pp. 339-349. doi:10.1109/SFCS.1982.58.
• [7] Suri S. The all-geodesic furthest neighbor problem for simple polygons. In: 1987 SoCG The third annual symposium on Computational geometry, Waterloo, Ontario, Canada, 08-10 June 1987. ACM, 1987 pp. 64-75. doi:10.1145/41958.41965.
• [8] Hershberger J, Suri S. Matrix Searching with the Shortest-Path Metric. SIAM Journal on Computing, 1997. 26(6):1612-1634. URL https://doi.org/10.1137/S0097539793253577.
• [9] Pollack R, Sharir M, Rote G. Computing the geodesic center of a simple polygon. Discrete and Computational Geometry, 1989. 4(6):611-626. doi:10.1007/BF02187751.
• [10] Asano T, Toussaint G. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, 1985.
• [11] Ahn HK, Barba L, Bose P, Carufel JLD, Korman M. A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon. Discrete and Computational Geometry, 2016. 56(4):836-859. doi:10.1007/s00454-016-9796-0.
• [12] Bae SW, Korman M, Okamoto Y. Computing the geodesic centers of a polygonal domain. Computational Geometry, 2015. 77:3-9. URL https://doi.org/10.1016/j.comgeo.2015.10.009.
• [13] Wang H. On the geodesic centers of polygonal domains. Journal of Computational Geometry, 2018. 9(1):131-190. URL https://doi.org/10.20382/jocg.v9i1a5.
• [14] Aronov B. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica, 1989. 4(1-4):109-140. doi:10.1007/BF01553882.
• [15] Papadopoulou E, Lee DT. Efficient computation of the geodesic Voronoi diagram of points in a simple polygon. In: 1995 ESA Third Annual European Symposium on Algorithms, Corfu, Greece, 25-27 September 1995. Springer, 1995 pp. 238-251. doi:10.1007/3-540-60313-1_147.
• [16] Aronov B, Fortune S, Wilfong G. The furthest-site geodesic Voronoi diagram. Discrete and Computational Geometry, 1993. 9(3):217-255. doi:10.1007/BF02189321.
• [17] Oh E, Barba L, Ahn HK. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. In: 2016 SoCG 32nd International Symposium on Computational Geometry (SoCG), Boston, Massachusetts, USA, 14-18 June 2016, Leibniz International Proceedings in Informatics (LIPIcs), volume 51. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016 pp. 1-15. doi:10.4230/LIPIcs.SoCG.2016.56.
• [18] Preparata FP, Shamos MI. Computational Geometry: an Introduction, Texts and Monographs in Computer Science. 1st Edition. Springer, 1985. ISBN:978-1-4612-1098-6.
• [19] Asano T, Mulzer W, Rote G, Wang Y. Constant-work-space algorithms for geometric problems. Journal of Computational Geometry, 2011. 2(1):46-68.
• [20] Korman M, Mulzer W, van Renssen A, Roeloffzen M, Seiferth P, Stein Y. Timespace trade-offs for triangulations and Voronoi diagrams. Computational Geometry, 2018. 73:35-45. doi:10.1016/j.comgeo.2017.01.001.
• [21] Raman V, Ramnath S. Improved upper bounds for time-space tradeoffs for selection with limited storage. In: 1998 SWAt 6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, 08-10 July 1998. Springer, 1998 pp. 131-142. ISBN:3-540-64682-5.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).