The complexity of many cells in arrangements of planes and related problems

DOI10.1007/BF02187785zbMath0691.68036MaRDI QIDQ582901

Leonidas J. Guibas, Herbert Edelsbrunner, Micha Sharir

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131112

zbMATH Keywords

computational geometryrandom sampling\(\epsilon \) -netsarrangements of planes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial geometries and geometric closure systems (51D20)

Related Items

On joints in arrangements of lines in space and related problems, The Szemerédi-Trotter theorem in the complex plane, Two theorems on point-flat incidences, Castles in the air revisited, Many-face complexity in incremental convex arrangements, A semi-algebraic version of Zarankiewicz's problem, Triangles in space or building (and analyzing) castles in the air, Lines in space: Combinatorics and algorithms, The exact fitting problem in higher dimensions, On the Minkowski distances and products of sum sets, A note on visibility-constrained Voronoi diagrams, New results for the growth of sets of real numbers, On a Question of Bourgain about Geometric Incidences, Combinatorial complexity bounds for arrangements of curves and spheres, A bichromatic incidence bound and an application, Counting facets and incidences, On the number of incidences between points and planes in three dimensions, COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS, The complexity and construction of many faces in arrangements of lines and of segments, New lower bounds for Hopcroft's problem, On the sum of squares of cell complexities in hyperplane arrangements

Cites Work

• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• Fast detection of polyhedral intersection
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• The upper envelope of piecewise linear functions: Tight bounds on the number of faces
• On the maximal number of edges of many faces in an arrangement
• The complexity of cells in three-dimensional arrangements
• \(\epsilon\)-nets and simplex range queries
• Finding the intersection of n half-spaces in time O(n log n)
• Implicitly representing arrangements of lines or segments
• New applications of random sampling in computational geometry
• A theorem on arrangements of lines in the plane
• Triangles in space or building (and analyzing) castles in the air
• How to search in history
• Constructing Arrangements of Lines and Hyperplanes with Applications