### Abstract

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},..., a_{d+1}) of X and the corresponding tuple (f(a _{1}), f((a_{2}),..., 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^{[3d/2]}) 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |

Publisher | Association for Computing Machinery |

Pages | 405-415 |

Number of pages | 11 |

ISBN (Print) | 9781611973389 |

DOIs | |

State | Published - 2014 |

Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
---|---|

Country | United States |

City | Portland, OR |

Period | 1/5/14 → 1/7/14 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'The complexity of order type isomorphism'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014*(pp. 405-415). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973402.30