The complexity of many cells in arrangements of planes and related problems
From MaRDI portal
Publication:582901
DOI10.1007/BF02187785zbMATH Open0691.68036MaRDI QIDQ582901FDOQ582901
Authors: Herbert Edelsbrunner, Leonidas Guibas, 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
Recommendations
- Cell complexities in hyperplane arrangements
- On the sum of squares of cell complexities in hyperplane arrangements
- On the complexity of arrangements of circles in the plane
- Cells with many facets in arrangements of hyperplanes
- scientific article
- Combinatorial simpliciality of arrangements of hyperplanes
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- scientific article; zbMATH DE number 177187
- Combinatorial complexity bounds for arrangements of curves and spheres
- scientific article; zbMATH DE number 3847039
Analysis of algorithms and problem complexity (68Q25) Combinatorial geometries and geometric closure systems (51D20)
Cites Work
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Extremal problems in discrete geometry
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing Arrangements of Lines and Hyperplanes with Applications
- The complexity and construction of many faces in arrangements of lines and of segments
- Implicitly representing arrangements of lines or segments
- Fast detection of polyhedral intersection
- On the maximal number of edges of many faces in an arrangement
- The complexity of cells in three-dimensional arrangements
- Finding the intersection of n half-spaces in time O(n log n)
- 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
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
Cited In (29)
- New lower bounds for Hopcroft's problem
- A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search
- Two theorems on point-flat incidences
- The exact fitting problem in higher dimensions
- COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
- A note on visibility-constrained Voronoi diagrams
- Title not available (Why is that?)
- On a Question of Bourgain about Geometric Incidences
- Title not available (Why is that?)
- Classification of arrangements by the number of their cells
- Combinatorial complexity bounds for arrangements of curves and spheres
- The complexity and construction of many faces in arrangements of lines and of segments
- The Szemerédi-Trotter theorem in the complex plane
- The complexity of cells in three-dimensional arrangements
- On the sum of squares of cell complexities in hyperplane arrangements
- Lines in space: Combinatorics and algorithms
- On the Minkowski distances and products of sum sets
- Enumerating colorings, tensions and flows in cell complexes
- Castles in the air revisited
- Many-face complexity in incremental convex arrangements
- A semi-algebraic version of Zarankiewicz's problem
- New results for the growth of sets of real numbers
- Depth in an arrangement of hyperplanes
- On the number of incidences between points and planes in three dimensions
- Triangles in space or building (and analyzing) castles in the air
- A bichromatic incidence bound and an application
- Counting facets and incidences
- On joints in arrangements of lines in space and related problems
- The Clarkson–Shor Technique Revisited and Extended
This page was built for publication: The complexity of many cells in arrangements of planes and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582901)
