Computing the link center of a simple polygon (Q1104086): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / author | |||
Property / author: William J. Lenhart / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Richard Pollack / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Subhash Suri / rank | |||
Normal rank | |||
Property / author | |||
Property / author: S. H. Whitesides / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Chee-Keng Yap / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q62037524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3787491 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Visibility and intersection problems in plane geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear algorithm for computing the visibility polygon from a point / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangulating a simple polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Euclidean shortest paths in the presence of rectilinear barriers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3290331 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing the geodesic center of a simple polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4299815227 / rank | |||
Normal rank |
Latest revision as of 10:29, 30 July 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
0 references