The Geodesic Diameter of Polygonal Domains

Details The Geodesic Diameter of Polygonal Domains The Geodesic Diameter of Polygonal Domains

2010-01-05

arxiv.org/abs/1001.0695v2

Computer Science

Computational Geometry

21 pages, 7 figures, preliminary version presented at ESA2010 and submitted to DCG

Scientific paper

This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.

Affiliated with

Also associated with

No associations

Rating

The Geodesic Diameter of Polygonal Domains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Geodesic Diameter of Polygonal Domains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Geodesic Diameter of Polygonal Domains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-540472