Minimum Average Distance Triangulations

DOI10.1007/978-3-642-33090-2_60MaRDI QIDQ2912886zbMATH OpenOpenAlexFDO

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1828

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

Cited in

(3)

This page was built for publication: Minimum Average Distance Triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912886)