Computing the link center of a simple polygon

ABSTRACT

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time &Ogr; (n2), where n is the number of sides of P. We also give an &Ogr;(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

REFERENCES

• AT1: Asano, A. and Toussaint, G.T. (1985). Computing the geodesic center of a simple polygon, Tech, Report SOCS-85.32, McGill University, see also Proc. US - Japan Seminar on Computer Science, Japan, June 1986.
• AT2: Avis, D. and Toussaint, G.T. (1981). An optimal algorithm for determining the visibility of a polygon from an edge, IEEE Trans. Computers C-30, pp. 910-914.
• Ch: Chazelle, B. (1982). A theorem on polygon cutting with applications, Proc. 23rd IEEE Symp. on Foundations of Computer Science, pp. 339-349.
• CG: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• EA: El Gindy, H. and Avis, D. (1981). A linear algorithm for computing the visibility polygon from a point, J. Algorithms 2, pp. 186-197.
• GJPT: Garey, M-R., Johnson, D.S., Preparata, F.P. and Tarjan, R.E. (1978). Triangulating a simple polygon, Inf. Proc. Letters 7, pp. 175- 180.
• G: Golumbic, M.C., Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980).
• GHLST: Guibas, L., Hershberger, J., Leven, D-9 Sharir, M., and Tarjan, R.E. (1986). Linear time algorithms for visibility and shortest path problems inside a triangulated simple polygon, Tech. Report 218, Comp. Sci. Dept., Courant Institute, April 1986.
• LP: Lee, D.T. and Preparata, F.P. (1984). Euclidean shortest paths in the presence of rectilinear barriers, Networks 14 (3), pp. 393-410.
• PS: Pollack, R. and Sharir, M. (1986). Computing the geodesic center of a simple polygon, Tech. Report 231, Comp. Sci. Dept., Courant Institute, July 1986.
• Sul: Suri, S. (1986). A polygon partitioning technique for link distance problems, Manuscript, Dept. of Comp. Science, Johns Hopkins University, November 1986.
• Su2: Suri, S. (1986). Computing all geodesic furthest neighbors of a simple polygon, Manuscript, Dept. of Comp. Science, Johns Hopkins University, November 1986.
• TV: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory