Pilz, Alexander ;
Welzl, Emo
Order on Order Types
Abstract
Given P and P', equally sized planar point sets in general position, we call a bijection from P to P' crossingpreserving if crossings of connecting segments in P are preserved in P' (extra crossings may occur in P'). If such a mapping exists, we say that P' crossingdominates P, and if such a mapping exists in both directions, P and P' are called crossingequivalent. The relation is transitive, and we have a partial order on the obtained equivalence classes (called crossing types or xtypes). Point sets of equal order type are clearly crossingequivalent, but not vice versa. Thus, xtypes are a coarser classification than order types. (We will see, though, that a collapse of different order types to one xtype occurs for sets with triangular convex hull only.)
We argue that either the maximal or the minimal xtypes are sufficient for answering many combinatorial (existential or extremal) questions on planar point sets. Motivated by this we consider basic properties of the relation. We characterize order types crossingdominated by points in convex position. Further, we give a full characterization of minimal and maximal abstract order types. Based on that, we provide a polynomialtime algorithm to check whether a point set crossingdominates another. Moreover, we generate all maximal and minimal xtypes for small numbers of points.
BibTeX  Entry
@InProceedings{pilz_et_al:LIPIcs:2015:5119,
author = {Alexander Pilz and Emo Welzl},
title = {{Order on Order Types}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {285299},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5119},
URN = {urn:nbn:de:0030drops51194},
doi = {10.4230/LIPIcs.SOCG.2015.285},
annote = {Keywords: point set, order type, planar graph, crossingfree geometric graph}
}
2015
Keywords: 

point set, order type, planar graph, crossingfree geometric graph 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 