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^{(d1)/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 epsilonapproximate the Minkowski sum of two given polytopes defined as the intersection of n halfspaces in O(n log(1/epsilon) + 1/epsilon^{(d1)/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 epsilonapproximate the width of a set of n points in O(n log(1/epsilon) + 1/epsilon^{(d1)/2 + alpha}) time, for any constant alpha > 0, a major improvement over the previous bound of roughly O(n + 1/epsilon^{d1}) 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:13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9466},
URN = {urn:nbn:de:0030drops94664},
doi = {10.4230/LIPIcs.ESA.2018.3},
annote = {Keywords: Minkowski sum, convex intersection, width, approximation}
}
2018
Keywords: 

Minkowski sum, convex intersection, width, approximation 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 