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)

Full work available at URL https://doi.org/10.1007/BF01285815

zbMATH Keywords

arrangement of \(n\) line segmentscombinatorial complexityEuclidean planemaximum number of edges

Mathematics Subject Classification ID

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

Review text

Associated with an arrangement of \(n\) line segments in the Euclidean plane is a subdivision of the plane consisting of vertices, edges and faces. It is proved that the maximum number of edges bounding \(m\) faces in an arrangement of \(n\) line segments in the plane is \(O(m^{2/3} n^{2/3}+n\alpha(n)+n \log m)\), with \(\alpha(n)\) the functional inverse of the Ackermann function.

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 general motion-planning problem with two degrees of freedom
• On the maximal number of edges of many faces in an arrangement
• On the Zone Theorem for Hyperplane Arrangements
• 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

(17)

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

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)