2026-07-24T18:14:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9466 2024-03-06T10:43:49Z ddc:004 open_access

Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums Arya, Sunil da Fonseca, Guilherme D. Mount, David M. Minkowski sum convex intersection width approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sunil Arya and Guilherme D. da Fonseca and David M. Mount 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.3 urn:nbn:de:0030-drops-94664 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode