# On Order Types of Random Point Sets

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, ...

https://hal.inria.fr/hal-01962093
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

v2.pdf
Files produced by the author(s)

### Identifiers

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

### Citation

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

Record views