Reconstructing sets of orthogonal line segments in the plane

F. Rendl; G.J. Woeginger

doi:10.1016/0012-365X(93)90124-C

Reconstructing sets of orthogonal line segments in the plane

F. Rendl, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	167-174
Number of pages	8
Journal	Discrete Mathematics
Volume	119
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(93)90124-C
Publication status	Published - 1993

Access to Document

10.1016/0012-365X(93)90124-C

Cite this

@article{68439e8202b04a6c95364c2fece9c39f,

title = "Reconstructing sets of orthogonal line segments in the plane",

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.",

author = "F. Rendl and G.J. Woeginger",

year = "1993",

doi = "10.1016/0012-365X(93)90124-C",

language = "English",

volume = "119",

pages = "167--174",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Reconstructing sets of orthogonal line segments in the plane

AU - Rendl, F.

AU - Woeginger, G.J.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

U2 - 10.1016/0012-365X(93)90124-C

DO - 10.1016/0012-365X(93)90124-C

M3 - Article

VL - 119

SP - 167

EP - 174

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -

Reconstructing sets of orthogonal line segments in the plane

Abstract

Access to Document

Fingerprint

Cite this