Loading...
Please wait, while we are loading the content...
Similar Documents
Computing the Geodesic L 1 -diameter and Center of a Simple Rectilinear Polygon
| Content Provider | Semantic Scholar |
|---|---|
| Author | Schuierer, Sven |
| Copyright Year | 1994 |
| Abstract | The diameter of a set S of points is the maximal distance between a pair of points in S. The center of S is the set of points that minimize the distance to their furthest neighbours. The problem of nding the diameter and center of a simple polygon with n vertices for diierent distance measures has been studied extensively in recent years. There are algorithms that run in linear time if the geodesic Euclidean metric is used and O(n log n) time if the link metric is used. In this paper we consider the L 1-metric inside a simple rectilinear polygon P, i.e., the distance between two points in P is deened as the length of the shortest rectilinear path between them. We give a linear time prune-and-search 215 algorithm to compute the L 1-diameter D(P) of P and a pair of vertices that span D(P). With the help of this vertex pair the center of P can also be computed in linear time. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Sven_Schuierer/publication/2781680_Computing_the_Geodesic_L_1_-Diameter_and_Center_of_a_Simple_Rectilinear_Polygon/links/0c96051e774279c52d000000.pdf |
| Alternate Webpage(s) | http://viadrina.euv-frankfurt-o.de/~wiwi-inf/wi/icci94/papers/a13.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
