Smoothed Analysis of Order Types

Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik

Research output: Contribution to journalArticleAcademic

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
Original languageEnglish
JournalarXiv.org
Publication statusPublished - 10 Jul 2019

Bibliographical note

15 pages, 6 figures, long introduction and short proofs

Keywords

  • cs.CG
  • cs.CC
  • cs.DM
  • cs.DS
  • math.CO

Fingerprint

Dive into the research topics of 'Smoothed Analysis of Order Types'. Together they form a unique fingerprint.

Cite this