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 : Let $P$ be a set of $n$ random points chosen uniformly in the unit square. In this paper, we examine the typical resolution of the order type of $P$. First, we show that with high probability, $P$ can be rounded to the grid of step $\frac{1}{n^{3+\epsilon}}$ without changing its order type. Second, we study algorithms for determining the order type of a point set in terms of the 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. Both results extend to more general models of random point sets.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Contributor : Xavier Goaoc <>
Submitted on : Thursday, September 12, 2019 - 6:26:14 PM
Last modification on : Friday, September 20, 2019 - 4:56:34 PM


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. 2019. ⟨hal-01962093v2⟩



Record views


Files downloads