Abstract
The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn).
Article PDF
Similar content being viewed by others
References
Asano, T., and Toussaint, G. T. (1985). Computing the geodesic center of a simple polygon, Technical Report SOCS-85.32, McGill University.
Chazelle, B. (1982). A theorem on polygon cutting with applications,Proc. 23rd IEEE Symp. on Foundations of Computer Science, pp. 339–349.
Dyer, M. E. (1984). Linear-time algorithms for two- and three-variable linear programs,SIAM J. Comput. 13, pp. 31–45.
Dyer, M. E. (1986). On a multidimensional search technique and its applications to the Euclidean one-center problem,SIAM J. Computing 15, pp. 725–738.
Garey, M. R., Johnson, D. S., Preparata, F. P., and Tarjan, R. E. (1978). Triangulating a simple polygon,Inform. Process. Lett. 7, pp. 175–180.
Guibas, L., Hershberger, J., Leven, D., Sharir, M., and Tarjan, R. E. (1987). Linear-time algorithms for visibility and shortest path problems inside a triangulated simple polygon,Algorithmica 2, pp. 209–233.
Lee, D. T., and Preparata, F. P. (1984). Euclidean shortest paths in the presence of rectilinear barriers,Networks 14(3), pp. 393–410.
Lenhart, W., Pollack, R., Sack, J., Seidel, R., Sharir, M., Suri, S., Toussaint, G. T., Yap, C., and Whitesides, S. (1987). Computing the link center of a simple polygon,Proc. 3rd ACM Symp. on Computational Geometry, pp. 1–10.
Megiddo, N. (1983). Linear-time algorithms for linear programming in R3 and related problems,SIAM J. Comput. 12, pp. 759–776.
Megiddo, N. (1983). Applying parallel computation algorithms in the design of serial algorithms,J. Assoc. Comput. Mach. 30, pp. 852–866.
Megiddo, N. (1984). Linear programming in linear time when the dimension is fixed,J. Assoc. Comput. Mach. 31, pp. 114–127.
Megiddo, N. (1989). On the ball spanned by balls,Discrete Comput. Geom., this issue, pp. 605–610.
Pollack, R., and Sharir, M. (1986). Computing the geodesic center of a simple polygon, Technical Report 231, Computer Science Department, Courant Institute, New York University, September 1986.
Suri, S. (1986). Computing the geodesic diameter of a simple polygon, Technical Report JHU/EECS-86/08, Department of Electrical Engineering and Computer Science, Johns Hopkins University.
Suri, S. (1986). Polygon partitioning techniques for link distance problems, Technical Report, Department of Electrical Engineering and Computer Science, Johns Hopkins University.
Tarjan, R. E., and Van Wyk, C. J. (1988). AnO(n log logn)-time algorithm for triangulating simple polygons,SIAM J. Comput. 17, pp. 143–178.
Zemel, E. (1984). AnO(n) algorithm for the linear multiple choice knapsack problem and related problems,Inform. Process. Lett. 18, pp. 123–128.
Author information
Authors and Affiliations
Additional information
Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Part of the work on this paper by the first two authors has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Work on this paper by the third author has been supported by the Fonds zur Förderung der wissenschaftlichen Forschung (FWF), Project S32/01.
Rights and permissions
About this article
Cite this article
Pollack, R., Sharir, M. & Rote, G. Computing the geodesic center of a simple polygon. Discrete Comput Geom 4, 611–626 (1989). https://doi.org/10.1007/BF02187751
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187751