Computing the link center of a simple polygon (Q1104086): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: William J. Lenhart / rank | |||
Property / author | |||
Property / author: Richard Pollack / rank | |||
Property / author | |||
Property / author: Subhash Suri / rank | |||
Property / author | |||
Property / author: S. H. Whitesides / rank | |||
Property / author | |||
Property / author: Chee-Keng Yap / rank | |||
Revision as of 12:02, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing the link center of a simple polygon |
scientific article |
Statements
Computing the link center of a simple polygon (English)
0 references
1988
0 references
The link center of a simple polygon \({\mathfrak P}\) is the set of points x inside \({\mathfrak P}\) at which the maximal link-distance from x to any other point in \({\mathfrak P}\) is minimized. Here the link distance between two points x, y inside \({\mathfrak P}\) is defined to be the smallest number of straight edges in a polygonal path inside \({\mathfrak P}\) connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time \(O(n^ 2)\), where n is the number of sides of \({\mathfrak P}\). We also give an O(n log n) algorithm for finding an approximate link center, that is, a point x such that the maximal link distance from x to any point in \({\mathfrak P}\) is at most one more than the value attained from the true link center.
0 references
link geodesics
0 references
visibility
0 references
computational geometry
0 references
simple polygon
0 references
approximate link center
0 references