#
The complexity of order type isomorphism

##
Michael Bannister

The order type of a point set in $R^d$ maps each
$(d{+}1)$-tuple of points to its orientation (e.g., clockwise or
counterclockwise in $R^2$). Two point sets $X$ and $Y$ have the same
order type if there exists a mapping $f$ from $X$ to $Y$ for which every
$(d{+}1)$-tuple $(a_1,a_2,\ldots,a_{d+1})$ of $X$ and the corresponding
tuple $(f(a_1),f(a_2),\ldots,f(a_{d+1}))$ in $Y$ have the same
orientation. In this paper we investigate the complexity of determining
whether two point sets have the same order type. We provide an $O(n^d)$
algorithm for this task, thereby improving upon the
$O(n^{\lfloor{3d/2}\rfloor})$ algorithm of Goodman and Pollack (1983).
The algorithm uses only order type queries and also works for abstract
order types (or acyclic oriented matroids). Our algorithm is optimal,
both in the abstract setting and for realizable points sets if the
algorithm only uses order type queries.

(From a paper at SODA 2014
by Greg Aloupis, John Iacono, Stefan Langerman, and Özgör
Özkan.)