Convex hulls of random order types

DOI10.1145/3570636MaRDI QIDQ6567268zbMATH OpenFDO

Authors Xavier Goaoc, Emo Welzl

Publication date 4 July 2024

Published in Journal of the ACM (Search for Journal in Brave)

zbMATH Keywords

oriented matroidprojective planeorder typerandom polytopeexcluded patternhairy ball theoremHadwiger's transversal theoremSylvester's four-point problemfinite subgroups of \(SO(3)\)sampling random order types

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Convex Hulls of Random Order Types
• On the distribution of order types
• Random polytopes in a convex polytope, independence of shape, and concentration of vertices
• On the variance of the number of extreme points of a random convex hull
• On the convex hull of random points in a polytope

Cites work

• scientific article; zbMATH DE number 3133224 (Why is no real title available?)
• scientific article; zbMATH DE number 4213489 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3475463 (Why is no real title available?)
• scientific article; zbMATH DE number 5019898 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A Ramsey property of order types
• Abstract order type extension and new results on the rectilinear crossing number
• Arrangements and Topological Planes
• Axioms and hulls
• Classroom examples of robustness problems in geometric computations
• Complete enumeration of small realizable oriented matroids
• Complexity of some geometric and topological problems
• Cones generated by random points on half-spheres and convex hulls of Poisson point processes
• Convex bodies, economic cap coverings, random polytopes
• Cutting convex curves
• Empty convex hexagons in planar point sets
• Enumerating order types for small point sets with applications
• Erdős--Szekeres theorem with forbidden order types
• Erdős-Szekeres theorem for point sets with forbidden subconfigurations
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal and probabilistic results for order types
• Finding sets of points without empty convex 6-gons
• Finding the Finite Groups of Symmetries of the Sphere
• Forbidden configurations in discrete geometry
• Hadwiger's Transversal Theorem In Higher Dimensions
• Limits of order types
• Lower Bounds for Approximation by Nonlinear Manifolds
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Multidimensional Sorting
• On the Erdős-Szekeres convex polygon problem
• On the Zone Theorem for Hyperplane Arrangements
• On the average complexity of the $k$-level
• On the distribution of order types
• On the finite group with a complete partition
• On the number of order types in integer grids of small size
• On the variance of random polytopes
• Oriented Matroids
• Oriented matroids
• Random points in halfspheres
• Random polytopes
• Random polytopes and the wet part for arbitrary probability distributions
• Regular simplices and Gaussian samples
• Sharp concentration of random polytopes
• Subquadratic encodings for point configurations
• The Complexity of Order Type Isomorphism
• The Intrinsic Spread of a Configuration in R d
• The Polygonal Regions into which a Plane is Divided by n Straight Lines
• The number of polytopes, configurations and real matroids
• The universality theorem for neighborly polytopes
• Topological planes
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II

Cited in

(5)

• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• Inscribable order types
• Orientation preserving maps of the square grid II
• Convex Hulls of Random Order Types

This page was built for publication: Convex hulls of random order types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6567268)