RECONSTRUCTING SETS OF ORTHOGONAL LINE SEGMENTS IN THE PLANE

Authors
RENDL F WOEGINGER G
Citation
F. Rendl et G. Woeginger, RECONSTRUCTING SETS OF ORTHOGONAL LINE SEGMENTS IN THE PLANE, Discrete mathematics, 119(1-3), 1993, pp. 167-174
Citations number
5
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
119
Issue
1-3
Year of publication
1993
Pages
167 - 174
Database
ISI
SICI code
0012-365X(1993)119:1-3<167:RSOOLS>2.0.ZU;2-O
Abstract
We show that reconstructing a set of n orthogonal line segments in the plane from the set of their vertices can be done in O(n log n) time, if the segments are allowed to cross. If the segments are not allowed to cross, the problem becomes NP-complete.