Loading...
Please wait, while we are loading the content...
Similar Documents
Computing the Constrained Euclidean, Geodesic and Link Centre of a Simple Polygon with Applications (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bose, Prosenjit Toussaint, Godfried |
| Abstract | Given an n vertex simple polygon M , we show how to compute the Euclidean center of M constrained to lie in the interior of M , in a polygonal region inside M or on the boundary of M in O(n log n + k) time where k is the number of intersections between M and the furthest point Voronoi diagram of the vertices of M . We show how to compute the geodesic center of M constrained to the boundary in O(n log n) time and the geodesic center of M constrained to lie in a polygonal region in O(n(n + k)) time where k is the number of intersections of the geodesic furthest point Voronoi diagram of M with the polygonal region. Furthermore, we show how to compute the link center of M constrained to the boundary of M in O(n log n) time. Finally, we show how to combine several of these criteria. For example, how to find the points whose maximum Euclidean and Link distance are minimized. Computing such locations has applications in such diverse fields as Geographic Information Systems (G.I.S.) and the ma... |
| File Format | |
| Journal | In Proc. of Pacific Graphics International |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Diverse Field Maximum Euclidean Polygonal Region Link Distance Link Centre Euclidean Center Geographic Information System Vertex Simple Polygon Link Center Simple Polygon Geodesic Center Point Voronoi Diagram Constrained Euclidean |
| Content Type | Text |
