Name
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. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1007/BF02187913 | Discrete & Computational Geometry - ACM Symposium on Computational Geometry, Waterloo |
Keywords | DocType | Volume |
Simple Polygon,Link Distance,Geodesic Path,Link Center,Polygonal Path | Conference | 3 |
Issue | ISSN | Citations |
3 | 0179-5376 | 36 |
PageRank | References | Authors |
3.48 | 9 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| william lenhart | 1 | 39 | 3.89 |
| Richard Pollack | 2 | 912 | 203.75 |
| j r sack | 3 | 36 | 3.48 |
| Raimund Seidel | 4 | 227 | 35.47 |
| Micha Sharir | 5 | 8405 | 1183.84 |