Show simple item record

dc.contributor.author
Barba, Luis
dc.contributor.author
Mulzer, Wolfgang
dc.contributor.editor
Fineman, Jeremy T.
dc.contributor.editor
Mitzenmacher, Michael
dc.date.accessioned
2019-10-31T13:07:44Z
dc.date.available
2019-10-30T18:18:52Z
dc.date.available
2019-10-31T13:04:56Z
dc.date.available
2019-10-31T13:07:44Z
dc.date.issued
2019
dc.identifier.isbn
978-3-95977-099-6
en_US
dc.identifier.issn
2190-6807
dc.identifier.other
10.4230/OASIcs.SOSA.2019.9
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/374043
dc.identifier.doi
10.3929/ethz-b-000374043
dc.description.abstract
We consider asymmetric convex intersection testing (ACIT). Let P subset R^d be a set of n points and H a set of n halfspaces in d dimensions. We denote by {ch(P)} the polytope obtained by taking the convex hull of P, and by {fh(H)} the polytope obtained by taking the intersection of the halfspaces in H. Our goal is to decide whether the intersection of H and the convex hull of P are disjoint. Even though ACIT is a natural variant of classic LP-type problems that have been studied at length in the literature, and despite its applications in the analysis of high-dimensional data sets, it appears that the problem has not been studied before. We discuss how known approaches can be used to attack the ACIT problem, and we provide a very simple strategy that leads to a deterministic algorithm, linear on n and m, whose running time depends reasonably on the dimension d.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
polytope intersection
en_US
dc.subject
LP-type problem
en_US
dc.subject
randomized algorithms
en_US
dc.title
Asymmetric Convex Intersection Testing
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
en_US
ethz.journal.title
OpenAccess Series in Informatics (OASIcs)
ethz.journal.volume
69
en_US
ethz.pages.start
9
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
en_US
ethz.event.location
San Diego, CA, USA
en_US
ethz.event.date
January 6–9, 2019
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
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::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
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::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.date.deposited
2019-10-30T18:19:03Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-10-31T13:05:07Z
ethz.rosetta.lastUpdated
2024-02-02T09:43:33Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Asymmetric%20Convex%20Intersection%20Testing&rft.jtitle=OpenAccess%20Series%20in%20Informatics%20(OASIcs)&rft.date=2019&rft.volume=69&rft.spage=9&rft.issn=2190-6807&rft.au=Barba,%20Luis&Mulzer,%20Wolfgang&rft.isbn=978-3-95977-099-6&rft.genre=proceeding&rft_id=info:doi/10.4230/OASIcs.SOSA.2019.9&rft.btitle=2nd%20Symposium%20on%20Simplicity%20in%20Algorithms%20(SOSA%202019)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record