The complexity of point configurations

DOI10.1016/0166-218X(91)90068-8zbMath0749.68041OpenAlexW2034752889MaRDI QIDQ1175788

Jacob E. Goodman, Richard Pollack

Publication date: 25 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90068-8

zbMATH Keywords

point configurationsorder typecombinatorial typeisotopy class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other designs, configurations (05B30) Configuration theorems in linear incidence geometry (51A20)

Related Items (10)

Drawing the Horton set in an integer grid of minimum size ⋮ A Ramsey property of order types ⋮ A Ramsey-Type Theorem in the Plane ⋮ On high-dimensional acyclic tournaments ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees ⋮ The complexity of order type isomorphism ⋮ Orientation preserving maps of the square grid II ⋮ Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees ⋮ Subquadratic Encodings for Point Configurations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Extremal problems in discrete geometry
• Semispaces of configurations, cell complexes of arrangements
• The number of small semispaces of a finite set of points in the plane
• More on k-sets of finite sets in the plane
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• A nonuniform matroid which violates the isotopy conjecture
• Solving systems of polynomial inequalities in subexponential time
• Uniform oriented matroids without the isotopy property
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• On the combinatorial classification of nondegenerate configurations in the plane
• Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
• Helly-type theorems for pseudoline arrangments in \(P^ 2\).
• A theorem of ordered duality
• 2N noncollinear points determine at least 2N directions
• Sur les matroides orientes de rang 3 et les arrangements de pseudodroites dans le plan projectif réel
• Computational synthetic geometry
• Oriented matroids
• Orientability of matroids
• On the number of line separations of a finite set in the plane
• Multidimensional Sorting
• Triangulations of Oriented Matroids and Convex Polytopes
• The number of polytopes, configurations and real matroids
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Sets of Directions Determined by n Points
• On the Betti Numbers of Real Varieties
• COLLINEARITY PROPERTIES OF SETS OF POINTS

This page was built for publication: The complexity of point configurations