The complexity of point configurations
From MaRDI portal
The authors consider three ways to generalize the notion of order of points on a line to higher dimensions. They give a survey on some recent results concerning complexity questions and efficient encoding for three types of such generalizations: combinatorial type, order type and isotopy class.
Recommendations
- The complexity of separating points in the plane
- The complexity of separating points in the plane
- scientific article; zbMATH DE number 5222518
- Computational complexity of fixed points and intersection points
- Finite point configurations in the plane, rigidity and Erdős problems
- scientific article; zbMATH DE number 1182894
- On matching point configurations
- On the complexity of arrangements of circles in the plane
- The probabilistic complexity of the Voronoi diagram of points on a polyhedron
- Complexity of some geometric and topological problems
Cites work
- 2N noncollinear points determine at least 2N directions
- A nonuniform matroid which violates the isotopy conjecture
- A theorem of ordered duality
- COLLINEARITY PROPERTIES OF SETS OF POINTS
- Computational synthetic geometry
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Extremal problems in discrete geometry
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- Helly-type theorems for pseudoline arrangments in P^ 2.
- scientific article; zbMATH DE number 3168302 (Why is no real title available?)
- scientific article; zbMATH DE number 3907263 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 4060217 (Why is no real title available?)
- scientific article; zbMATH DE number 4092241 (Why is no real title available?)
- scientific article; zbMATH DE number 3779340 (Why is no real title available?)
- scientific article; zbMATH DE number 4114647 (Why is no real title available?)
- scientific article; zbMATH DE number 3394958 (Why is no real title available?)
- scientific article; zbMATH DE number 3407703 (Why is no real title available?)
- Lower Bounds for Approximation by Nonlinear Manifolds
- More on k-sets of finite sets in the plane
- Multidimensional Sorting
- On the Betti Numbers of Real Varieties
- On the combinatorial classification of nondegenerate configurations in the plane
- On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
- On the number of line separations of a finite set in the plane
- On the Sets of Directions Determined by n Points
- Orientability of matroids
- Oriented matroids
- Proof of a conjecture of Burr, Grünbaum, and Sloane
- Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
- Semispaces of configurations, cell complexes of arrangements
- Solving systems of polynomial inequalities in subexponential time
- Sur les matroides orientes de rang 3 et les arrangements de pseudodroites dans le plan projectif réel
- The number of polytopes, configurations and real matroids
- The number of small semispaces of a finite set of points in the plane
- Triangulations of Oriented Matroids and Convex Polytopes
- Uniform oriented matroids without the isotopy property
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
Cited in
(17)- A Ramsey property of order types
- Drawing the Horton set in an integer grid of minimum size
- Cross-sections of line configurations in \(\mathbb{R}^3\) and (\(d-2\))-flat configurations in \(\mathbb{R}^d\)
- Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- scientific article; zbMATH DE number 431988 (Why is no real title available?)
- Constructions for large spatial point-line (n_k) congurations
- On high-dimensional acyclic tournaments
- A Ramsey-Type Theorem in the Plane
- Subquadratic encodings for point configurations
- Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
- scientific article; zbMATH DE number 4182820 (Why is no real title available?)
- The complexity of order type isomorphism
- Orientation preserving maps of the square grid II
- Order-forcing in neural codes
- Orientation preserving maps of the square grid
- Crossing and non-crossing families
This page was built for publication: The complexity of point configurations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1175788)
