License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.3
URN: urn:nbn:de:0030-drops-94664
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9466/
Arya, Sunil ;
da Fonseca, Guilherme D. ;
Mount, David M.
Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums
Abstract
Approximation problems involving a single convex body in R^d have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions d <= 3 and/or do not consider approximation. In this paper, we consider approximations to two natural problems involving multiple convex bodies: detecting whether two polytopes intersect and computing their Minkowski sum. Given an approximation parameter epsilon > 0, we show how to independently preprocess two polytopes A,B subset R^d into data structures of size O(1/epsilon^{(d-1)/2}) such that we can answer in polylogarithmic time whether A and B intersect approximately. More generally, we can answer this for the images of A and B under affine transformations. Next, we show how to epsilon-approximate the Minkowski sum of two given polytopes defined as the intersection of n halfspaces in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0. Finally, we present a surprising impact of these results to a well studied problem that considers a single convex body. We show how to epsilon-approximate the width of a set of n points in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0, a major improvement over the previous bound of roughly O(n + 1/epsilon^{d-1}) time.
BibTeX - Entry
@InProceedings{arya_et_al:LIPIcs:2018:9466,
author = {Sunil Arya and Guilherme D. da Fonseca and David M. Mount},
title = {{Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {3:1--3:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9466},
URN = {urn:nbn:de:0030-drops-94664},
doi = {10.4230/LIPIcs.ESA.2018.3},
annote = {Keywords: Minkowski sum, convex intersection, width, approximation}
}
|
Keywords: |
|
Minkowski sum, convex intersection, width, approximation |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
