Smoothed Analysis of Order Types

Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik

Consider an ordered point set $P=(p_1,\dots ,p_n)$, its order type (denoted by ${\chi }_P$) is a map which assigns to every triple of points a value in $\{+,-,0\}$ based on whether the…