Reconstructing sets of orthogonal line segments in the plane

F. Rendl, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)167-174
    Number of pages8
    JournalDiscrete Mathematics
    Volume119
    Issue number1-3
    DOIs
    Publication statusPublished - 1993

    Fingerprint Dive into the research topics of 'Reconstructing sets of orthogonal line segments in the plane'. Together they form a unique fingerprint.

    Cite this