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

DOI10.1007/BF01285815zbMath0768.52003MaRDI QIDQ1200271

Micha Sharir, Boris Aronov, Leonidas J. Guibas, Herbert Edelsbrunner

Publication date: 17 January 1993

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

Euclidean planecombinatorial complexitymaximum 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)

Related Items

Solving the minimum convex partition of point sets with integer programming, Triangles in space or building (and analyzing) castles in the air, The common exterior of convex polygons in the plane, Connected component and simple polygon intersection searching, Drawing graphs using a small number of obstacles, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, A tail estimate for Mulmuley's segment intersection algorithm, Topological sweep of the complete graph

Cites Work

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