The Complexity of Order Type Isomorphism

DOI10.1137/1.9781611973402.30MaRDI QIDQ5383989zbMATH OpenOpenAlexFDO

Authors Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, Stefanie Wuhrer

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.0928

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

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,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^{lfloor3d/2floor})$ 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.

Recommendations

• scientific article; zbMATH DE number 512933
• On the complexity of partial order properties
• The computational complexity of equivalence and isomorphism problems
• The complexity of isomorphism for complete theories of linear orders with unary predicates
• On the Arithmetic of Order Types
• Randomised algorithms for isomorphisms of simple types
• Efficient algorithms for isomorphisms of simple types
• Efficient algorithms for isomorphisms of simple types

Cited in

(14)

• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Extreme point and halving edge search in abstract order types
• Drawing the almost convex set in an integer grid of minimum size
• scientific article; zbMATH DE number 3907241 (Why is no real title available?)
• Reprint of: Extreme point and halving edge search in abstract order types
• Subquadratic encodings for point configurations
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Order on order types
• An optimal algorithm for reconstructing point set order types from radial orderings
• scientific article; zbMATH DE number 4182820 (Why is no real title available?)
• Clique-width of point configurations
• Bicolored order types
• Convex hulls of random order types
• The complexity of order type isomorphism

This page was built for publication: The Complexity of Order Type Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383989)