Geodesic diameter of a polygonal domain in O(n^4 log n) time

Details Geodesic diameter of a polygonal domain in O(n^4 log n) time Geodesic diameter of a polygonal domain in O(n^4 log n) time

2010-06-10

arxiv.org/abs/1006.1998v2

Computer Science

Computational Geometry

NOTE: It has turned out that, unfortunately, Lemma 2 does not hold, which renders the main result incorrect

Scientific paper

We show that the geodesic diameter of a polygonal domain with n vertices can
be computed in O(n^4 log n) time by considering O(n^3) candidate diameter
endpoints; the endpoints are a subset of vertices of the overlay of shortest
path maps from vertices of the domain.

Affiliated with

Also associated with

No associations

Rating

Geodesic diameter of a polygonal domain in O(n^4 log n) time 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 Geodesic diameter of a polygonal domain in O(n^4 log n) time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geodesic diameter of a polygonal domain in O(n^4 log n) time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492015