Minimum Average Distance Triangulations

Details Minimum Average Distance Triangulations Minimum Average Distance Triangulations

2011-12-08

arxiv.org/abs/1112.1828v2

Computer Science

Computational Geometry

Scientific paper

We study the problem of finding a triangulation T of a planar point set S such as to minimize the expected distance between two points x and y chosen uniformly at random from S. By distance we mean the length of the shortest path between x and y along edges of T. The length of a path is the sum of the weights of its edges. Edge weights are assumed to be given as part of the problem for every pair of distinct points (x,y) in S^2. In a different variant of the problem, the points are vertices of a simple polygon and we look for a triangulation of the interior of the polygon that is optimal in the same sense. We prove that a general formulation of the problem in which the weights are arbitrary positive numbers is strongly NP-complete. For the case when all the weights are equal we give polynomial-time algorithms. In the end we mention several open problems.

Affiliated with

Also associated with

No associations

Rating

Minimum Average Distance Triangulations 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 Minimum Average Distance Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Average Distance Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-547956