The complexity of order type isomorphism

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    PublisherAssociation for Computing Machinery
    Pages405-415
    Number of pages11
    ISBN (Print)9781611973389
    DOIs
    StatePublished - 2014
    Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
    Duration: Jan 5 2014Jan 7 2014

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    CountryUnited States
    CityPortland, OR
    Period1/5/141/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

    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 (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