Next:
ND59 MINIMUM SEPARATING
Up:
Miscellaneous
Previous:
ND57 MINIMUM BEND
-
I
NSTANCE
:
Collection
of pairs of integers giving the
coordinates of
n
points in the plane.
-
S
OLUTION
:
A triangulation of the set of points represented by
C
, i.e., a collection
E
of non-intersecting line segments each joining two points in
C
that divides
the interior of the convex hull into triangular regions.
-
M
EASURE
:
The discrete-Euclidean length of the triangulation, i.e.,
-
Good News:
Approximable within
[
294
].
-
Comment:
Note that the problem is not known to be NP-complete.
For a convex point set the problem is approximable within 12 [
294
].
The Steiner variation in which the point set of
E
must be a superset of
C
is approximable within 316 [
96
].
-
Garey and Johnson:
OPEN12
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997