✦ LIBER ✦

Reconstructing sets of orthogonal line segments in the plane

✍ Scribed by Franz Rendl; Gerhard Woeginger

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 550 KB
Volume: 119
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90124-c

No coin nor oath required. For personal study only.

✦ Synopsis

Rend], F. and G. Woeginger, Reconstructing sets of orthogonal line segments in the plane, Discrete Mathematics 119 (1993) 1677174.

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.

📜 SIMILAR VOLUMES

On illuminating line segments in the pla

On illuminating line segments in the plane

✍ Jurek Czyzowicz; Eduardo Rivera-Campo; Jorge Urrutia; Joseph Zaks 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

Let F be a family of n convex sets in the plane. A set of light sources S illuminates F if every point on the boundary of each element of F is visible from at least one element in S. We prove that if F is a family of n line segments, n >/11, then [-2n/3 7 light sources are always sufficient to illum

Computing the full visibility graph of a

Computing the full visibility graph of a set of line segments

✍ S.K. Wismath 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 419 KB

Minimal Diameter of Certain Sets in the

Minimal Diameter of Certain Sets in the Plane

✍ András Bezdek; Ferenc Fodor 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 91 KB

We investigate the problem of finding the smallest diameter D(n) of a set of n points such that all the mutual distances between them are at least 1. The asymptotic behaviour of D(n) is known; the exact value of D(n) can be easily found up to 6 points. Bateman and Erdo s proved that D(7)=2. In this

On the in-plane motion of thin, rotating

On the in-plane motion of thin, rotating ring segments

✍ H.E. Williams 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 1019 KB

On the distribution of distances in fini

On the distribution of distances in finite sets in the plane

✍ K Vesztergombi 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 894 KB

Let n k denote the number of times the kth largest distance occurs among a set S of n points. We show that if S is the set of vertices of a convex polygone in the euclidean plane, then n1+2n2~3n and n2<~n +n 1. Together with the well-known inequality n~<~n and the trivial inequalities n~>~O and n2>~

K2 of n lines in the plane

✍ Barry H. Dayton; Leslie G. Roberts 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 869 KB