Show simple item record

dc.contributor.author
Pilz, Alexander
dc.contributor.author
Welzl, Emo
dc.contributor.author
Wettstein, Manuel
dc.contributor.editor
Aronov, Boris
dc.contributor.editor
Katz, Matthew J.
dc.date.accessioned
2017-12-05T14:09:39Z
dc.date.available
2017-10-06T04:42:42Z
dc.date.available
2017-10-17T11:54:02Z
dc.date.available
2017-12-05T14:09:39Z
dc.date.issued
2017
dc.identifier.isbn
978-3-95977-038-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SoCG.2017.54
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/192198
dc.identifier.doi
10.3929/ethz-b-000192198
dc.description.abstract
A set P = H cup {w} of n+1 points in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on P, it suffices to know the so-called frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles, and many more. Based on these formulas, the corresponding numbers of graphs can be computed efficiently. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of simplices spanned by H that contain w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions. The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d log n). Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in R^d in time O(n^max(omega,k-2)) where omega = 2.373, even though the asymptotic number of facets may be as large as n^k.
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
geometric graph
en_US
dc.subject
wheel set
en_US
dc.subject
simplicial depth
en_US
dc.subject
Gale transform
en_US
dc.subject
polytope
en_US
dc.title
From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
33rd International Symposium on Computational Geometry (SoCG 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
77
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
54
en_US
ethz.size
16 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
33rd International Symposium on Computational Geometry (SoCG 2017)
en_US
ethz.event.location
Brisbane, Australia
en_US
ethz.event.date
July 4-7, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Saarbrücken/Wadern
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
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-10-06T04:42:48Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-10-17T11:54:04Z
ethz.rosetta.lastUpdated
2019-02-02T13:51:34Z
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=From%20crossing-free%20graphs%20on%20wheel%20sets%20to%20embracing%20simplices%20and%20polytopes%20with%20few%20vertices&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2017&rft.volume=77&rft.spage=54&rft.issn=1868-8969&rft.au=Pilz,%20Alexander&Welzl,%20Emo&Wettstein,%20Manuel&rft.isbn=978-3-95977-038-5&rft.genre=proceeding&rft_id=info:doi/978-3-95977-038-5&rft.btitle=33rd%20International%20Symposium%20on%20Computational%20Geometry%20(SoCG%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record