Smoothed Analysis of Order Types

Abstract

Consider an ordered point set $P = (p_1,\ldots,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 points are collinear(0), oriented clockwise(-) or counter-clockwise(+). An abstract order type is a map $\chi : \left[\substack{n\\3}\right] \rightarrow \{+,-,0\}$ (where $\left[\substack{n\\3}\right]$ is the collection of all triples of a set of $n$ elements) that satisfies the following condition: for every set of five elements $S\subset [n]$ its induced order type $\chi_{|S}$ is realizable by a point set. To be precise, a point set $P$ realizes an order type $\chi$,if $\chi_P(p_i,p_j,p_k) = \chi(i,j,k)$, for all $i