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.
Original language | English |
---|---|
Pages (from-to) | 167-174 |
Number of pages | 8 |
Journal | Discrete Mathematics |
Volume | 119 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 1993 |