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

DOI10.1007/BF01285815MaRDI QIDQ1200271zbMATH OpenFDO

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

Publication date 17 January 1993

Published in Combinatorica (Search for Journal in Brave)

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)

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

Cites work

• A theorem on arrangements of lines in the plane
• Applications of random sampling in computational geometry. II
• Combinatorial complexity bounds for arrangements of curves and spheres
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Construction of \(\epsilon\)-nets
• On the Zone Theorem for Hyperplane Arrangements
• On the general motion-planning problem with two degrees of freedom
• 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
• The complexity and construction of many faces in arrangements of lines and of segments
• Triangles in space or building (and analyzing) castles in the air

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
• Corrigendum to: ``On disjoint concave chains in arrangements of (pseudo) lines
• Wedges in Euclidean Arrangements
• 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)