ausblenden:
Schlagwörter:
Computer Science, Computational Geometry, cs.CG
Zusammenfassung:
A rectangular partition is the partition of an (axis-aligned) rectangle into
interior-disjoint rectangles. We ask whether a rectangular partition permits a
"nice" drawing of its dual, that is, a straight-line embedding of it such that
each dual vertex is placed into the rectangle that it represents. We show that
deciding whether such a drawing exists is NP-complete. Moreover, we consider
the drawing where a vertex is placed in the center of the represented rectangle
and consider sufficient conditions for this drawing to be nice. This question
is studied both in the plane and for the higher-dimensional generalization of
rectangular partitions.
