The complexity of many cells in arrangements of planes and related problems
The techniques developed in a companion paper by the same authors are extended to problems involving arrangements of planes in three dimensions or hyperplanes in higher dimensions. The problems are decomposed into subproblems of smaller size, random sampling and \(\epsilon\)-nets are used. The complexity of many cells in arrangements of planes in three dimensions is analyzed and an efficient worst-case algorithm for their calculation is presented. Also the following simpler problems are studied: Count the maximum number of incidences between planes and vertices of their arrangement (a randomized algorithm for their calculation is given); obtain an upper bound on the number of incidences between these points and planes, assuming that no three points are collinear; determine for each of given m points the plane of a given set of planes lying immediately below it. Count the maximum number of facets bounding m distinct cells in an arrangement of n hyperplanes in d dimensions \((d>3)\).
- 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; zbMATH DE number 4151859
- 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
- -nets and simplex range queries
- A theorem on arrangements of lines in the plane
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Extremal problems in discrete geometry
- Fast detection of polyhedral intersection
- Finding the intersection of n half-spaces in time O(n log n)
- How to search in history
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- New applications of random sampling in computational geometry
- 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
- The complexity of cells in three-dimensional arrangements
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
- Triangles in space or building (and analyzing) castles in the air
- The complexity of cells in three-dimensional arrangements
- Counting facets and incidences
- Classification of arrangements by the number of their cells
- Depth in an arrangement of hyperplanes
- On the sum of squares of cell complexities in hyperplane arrangements
- On joints in arrangements of lines in space and related problems
- Castles in the air revisited
- Many-face complexity in incremental convex arrangements
- On the number of incidences between points and planes in three dimensions
- New lower bounds for Hopcroft's problem
- Lines in space: Combinatorics and algorithms
- The exact fitting problem in higher dimensions
- Enumerating colorings, tensions and flows in cell complexes
- A semi-algebraic version of Zarankiewicz's problem
- Triangles in space or building (and analyzing) castles in the air
- The Szemerédi-Trotter theorem in the complex plane
- scientific article; zbMATH DE number 4151859 (Why is no real title available?)
- On a Question of Bourgain about Geometric Incidences
- A note on visibility-constrained Voronoi diagrams
- A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search
- COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
- scientific article; zbMATH DE number 1383707 (Why is no real title available?)
- The Clarkson–Shor Technique Revisited and Extended
- The complexity and construction of many faces in arrangements of lines and of segments
- A bichromatic incidence bound and an application
- On levels in arrangements and Voronoi diagrams
- Two theorems on point-flat incidences
- On the Minkowski distances and products of sum sets
- New results for the growth of sets of real numbers
- Combinatorial complexity bounds for arrangements of curves and spheres
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)
