The complexity of order type isomorphism

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

doi:10.1137/1.9781611973402.30

The complexity of order type isomorphism

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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^[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	https://doi.org/10.1137/1.9781611973402.30
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/Territory	United States
City	Portland, OR
Period	1/5/14 → 1/7/14

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

10.1137/1.9781611973402.30

Cite this

The complexity of order type isomorphism. / Aloupis, Greg; Iacono, John; Langerman, Stefan et al.

Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. p. 405-415 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aloupis, G, Iacono, J, Langerman, S, Özkan, Ö & Wuhrer, S 2014, The complexity of order type isomorphism. in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 405-415, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14. https://doi.org/10.1137/1.9781611973402.30

@inproceedings{e5874ded70344b3d9e03d1927be968d2,

title = "The complexity of order type isomorphism",

abstract = "The order type of a point set in Rd 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 (a1, a 2,..., ad+1) of X and the corresponding tuple (f(a 1), f((a2),..., f(ad+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 (nd) 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.",

author = "Greg Aloupis and John Iacono and Stefan Langerman and {\"O}zg{\"u}r {\"O}zkan and Stefanie Wuhrer",

year = "2014",

doi = "10.1137/1.9781611973402.30",

language = "English (US)",

isbn = "9781611973389",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "405--415",

booktitle = "Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014",

note = "25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 ; Conference date: 05-01-2014 Through 07-01-2014",

}

TY - GEN

T1 - The complexity of order type isomorphism

AU - Aloupis, Greg

AU - Iacono, John

AU - Langerman, Stefan

AU - Özkan, Özgür

AU - Wuhrer, Stefanie

PY - 2014

Y1 - 2014

N2 - The order type of a point set in Rd 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 (a1, a 2,..., ad+1) of X and the corresponding tuple (f(a 1), f((a2),..., f(ad+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 (nd) 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.

AB - The order type of a point set in Rd 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 (a1, a 2,..., ad+1) of X and the corresponding tuple (f(a 1), f((a2),..., f(ad+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 (nd) 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.

UR - http://www.scopus.com/inward/record.url?scp=84902106686&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902106686&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.30

DO - 10.1137/1.9781611973402.30

M3 - Conference contribution

AN - SCOPUS:84902106686

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 405

EP - 415

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

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

Y2 - 5 January 2014 through 7 January 2014

ER -

The complexity of order type isomorphism

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this