The number of edges of many faces in a line segment arrangement

DOI10.1007/BF01285815zbMATH Open0768.52003MaRDI QIDQ1200271FDOQ1200271

Authors: Boris Aronov, Leonidas Guibas, Micha Sharir, Herbert Edelsbrunner 

Publication date: 17 January 1993

Published in: Combinatorica (Search for Journal in Brave)

Recommendations

• On the maximal number of edges of many faces in an arrangement
• The complexity and construction of many faces in arrangements of lines and of segments
• Arrangements of segments that share endpoints: Single face results
• Multicolor combination lemma
• Computing a Face in an Arrangement of Line Segments and Related Problems

zbMATH Keywords

combinatorial complexityEuclidean planemaximum number of edgesarrangement of \(n\) line segments

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other problems of combinatorial convexity (52A37) Homomorphism, automorphism and dualities in linear incidence geometry (51A10)

Cites Work

• Applications of random sampling in computational geometry. II
• Combinatorial complexity bounds for arrangements of curves and spheres
• On the general motion-planning problem with two degrees of freedom
• Constructing Arrangements of Lines and Hyperplanes with Applications
• The complexity and construction of many faces in arrangements of lines and of segments
• On the Zone Theorem for Hyperplane Arrangements
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• On the maximal number of edges of many faces in an arrangement
• Separating two simple polygons by a sequence of translations
• A theorem on arrangements of lines in the plane
• Triangles in space or building (and analyzing) castles in the air
• Construction of \(\epsilon\)-nets

Cited In (15)

• Solving the minimum convex partition of point sets with integer programming
• The complexity and construction of many faces in arrangements of lines and of segments
• On the boundary of the union of planar convex sets
• On the maximal number of edges of many faces in an arrangement
• The complexity of the outer face in arrangements of random segments
• Wedges in Euclidean Arrangements
• Corrigendum to: ``On disjoint concave chains in arrangements of (pseudo) lines
• Connected component and simple polygon intersection searching
• On disjoint concave chains in arrangements of (pseudo) lines
• Topological sweep of the complete graph
• Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
• Triangles in space or building (and analyzing) castles in the air
• The common exterior of convex polygons in the plane
• Arrangements of segments that share endpoints: Single face results
• A tail estimate for Mulmuley's segment intersection algorithm

This page was built for publication: The number of edges of many faces in a line segment arrangement

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