Next:
MS9 MINIMUM SORTING
Up:
Miscellaneous
Previous:
MS7 MINIMUM SIZE
-
I
NSTANCE
:
Rectangle
R
and finite set
P
of points located inside
R
.
-
S
OLUTION
:
A set of line segments that partition
R
into rectangles such that
every point in
P
is on the boundary of some rectangle.
-
M
EASURE
:
The total length of the introduced line segments.
-
Good News:
Approximable within 1.75 [
140
].
-
Comment:
Variation in which
R
is a rectilinear polygon is approximable within 4
[
141
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997