Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On Order Types of Random Point Sets

Olivier Devillers 1 Philippe Duchon 2 Marc Glisse 3 Xavier Goaoc 1
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : A simple method to produce a random order type is to take the order type of a random point set. We conjecture that many probability distributions on order types defined in this way are heavily concentrated and therefore sample inefficiently the space of order types. We present two results on this question. First, we study experimentally the bias in the order types of $n$ random points chosen uniformly and independently in a square, for $n$ up to $16$. Second, we study algorithms for determining the order type of a point set in terms of the number of coordinate bits they require to know. We give an algorithm that requires on average $4n \log_2 n+O(n)$ bits to determine the order type of $P$, and show that any algorithm requires at least $4n \log_2 n - O(n \log\log n)$ bits. This implies that the concentration conjecture cannot be proven by an ``efficient encoding'' argument.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Xavier Goaoc <>
Submitted on : Thursday, May 28, 2020 - 5:04:46 PM
Last modification on : Thursday, June 11, 2020 - 4:19:22 AM


Files produced by the author(s)


  • HAL Id : hal-01962093, version 2
  • ARXIV : 1812.08525


Olivier Devillers, Philippe Duchon, Marc Glisse, Xavier Goaoc. On Order Types of Random Point Sets. 2020. ⟨hal-01962093v2⟩



Record views


Files downloads