Reconstructing sets of orthogonal line segments in the plane

DOI10.1016/0012-365X(93)90124-CMaRDI QIDQ688265zbMATH OpenFDO

Authors Franz Rendl, Gerhard J. Woeginger

Publication date 7 February 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90124-C

zbMATH Keywords

computational geometryorthogonal line segments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Orthogonal polygon reconstruction from stabbing information
• Reconstruction of Weakly Simple Polygons from Their Edges
• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
• Reconstructing orthogonal polyhedra from putative vertex sets

Cites work

• scientific article; zbMATH DE number 4062601 (Why is no real title available?)
• scientific article; zbMATH DE number 8793 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(8)

• The complexity of detecting crossingfree configurations in the plane
• Winner determination in geometrical combinatorial auctions
• A bottleneck matching problem with edge-crossing constraints
• Reconstruction of Concurrent Lines from Leaning Points
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• scientific article; zbMATH DE number 4062601 (Why is no real title available?)
• Configurations with few crossings in topological graphs
• Matching points with rectangles and squares

This page was built for publication: Reconstructing sets of orthogonal line segments in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688265)