Show simple item record

dc.contributor.author
Pilz, Alexander
dc.contributor.author
Welzl, Emo
dc.contributor.editor
Arge, Lars
dc.contributor.editor
Pach, János
dc.date.accessioned
2019-07-18T07:33:33Z
dc.date.available
2017-06-11T22:49:10Z
dc.date.available
2019-07-18T07:33:33Z
dc.date.issued
2015
dc.identifier.isbn
978-3-939897-83-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SOCG.2015.285
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/109758
dc.identifier.doi
10.3929/ethz-b-000109758
dc.description.abstract
Given P and P', equally sized planar point sets in general position, we call a bijection from P to P' crossing-preserving 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' crossing-dominates P, and if such a mapping exists in both directions, P and P' are called crossing-equivalent. The relation is transitive, and we have a partial order on the obtained equivalence classes (called crossing types or x-types). Point sets of equal order type are clearly crossing-equivalent, but not vice versa. Thus, x-types are a coarser classification than order types. (We will see, though, that a collapse of different order types to one x-type occurs for sets with triangular convex hull only.) We argue that either the maximal or the minimal x-types 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 crossing-dominated by points in convex position. Further, we give a full characterization of minimal and maximal abstract order types. Based on that, we provide a polynomial-time algorithm to check whether a point set crossing-dominates another. Moreover, we generate all maximal and minimal x-types for small numbers of points.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Point set
en_US
dc.subject
Order type
en_US
dc.subject
Planar graph
en_US
dc.subject
Crossing-free geometric graph
en_US
dc.title
Order on order types
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
31st International Symposium on Computational Geometry (SoCG 2015)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
34
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
285
en_US
ethz.pages.end
299
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
31st International Symposium on Computational Geometry (SoCG 2015)
en_US
ethz.event.location
Eindhoven, The Netherlands
en_US
ethz.event.date
June 22-25, 2015
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl, Germany
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
ethz.date.deposited
2017-06-11T22:49:34Z
ethz.source
ECIT
ethz.identifier.importid
imp593653e80436f32692
ethz.ecitpid
pub:170884
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-31T12:14:36Z
ethz.rosetta.lastUpdated
2019-07-18T07:33:42Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Order%20on%20order%20types&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2015&rft.volume=34&rft.spage=285&rft.epage=299&rft.issn=1868-8969&rft.au=Pilz,%20Alexander&Welzl,%20Emo&rft.isbn=978-3-939897-83-5&rft.genre=proceeding&rft_id=info:doi/978-3-939897-83-5&rft.btitle=31st%20International%20Symposium%20on%20Computational%20Geometry%20(SoCG%202015)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record