The Complexity of Order Type Isomorphism

2013/11/04 by Greg Aloupis, Aloupis, Greg, John Iacono +5
Computer Science · #Algorithms and Data Compression #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1311.0928

Preliminary version of paper to appear at ACM-SIAM Symposium on Discrete Algorithms (SODA14)

arxiv created 2013/11/04 · openalex publication_date 2013/11/04 · arxiv updated 2013/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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²). 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₁,a₂,…,a_d+1) of X and the corresponding tuple (f(a₁),f(a₂),…,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^\lfloor3d/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.

Related

• Smoothed Analysis of Order Types
• Bicolored Order Types
• Subquadratic Encodings for Point Configurations
• Inscribable order types
• On the Complexity of Polytope Isomorphism Problems