Bergold, Helena ;
Bertschinger, Daniel ;
Grelier, Nicolas ;
Mulzer, Wolfgang ;
Schnider, Patrick
WellSeparation and Hyperplane Transversals in High Dimensions
Abstract
A family of k point sets in d dimensions is wellseparated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Wellseparation is a strong assumption that allows us to conclude that certain kinds of generalized hamsandwich cuts for the point sets exist. But how hard is it to check if a given family of highdimensional point sets has this property? Starting from this question, we study several algorithmic aspects of the existence of transversals and separations in highdimensions.
First, we give an explicit proof that k point sets are wellseparated if and only if their convex hulls admit no (k  2)transversal, i.e., if there exists no (k  2)dimensional flat that intersects the convex hulls of all k sets. It follows that the task of checking wellseparation lies in the complexity class coNP. Next, we show that it is NPhard to decide whether there is a hyperplanetransversal (that is, a (d  1)transversal) of a family of d + 1 line segments in ℝ^d, where d is part of the input. As a consequence, it follows that the general problem of testing wellseparation is coNPcomplete. Furthermore, we show that finding a hyperplane that maximizes the number of intersected sets is NPhard, but allows for an Ω((log k)/(k log log k))approximation algorithm that is polynomial in d and k, when each set consists of a single point. When all point sets are finite, we show that checking whether there exists a (k  2)transversal is in fact strongly NPcomplete.
Finally, we take the viewpoint of parametrized complexity, using the dimension d as a parameter: given k convex sets in ℝ^d, checking whether there is a (k2)transversal is FPT with respect to d. On the other hand, for k ≥ d+1 finite point sets in ℝ^d, it turns out that checking whether there is a (d1)transversal is W[1]hard with respect to d.
BibTeX  Entry
@InProceedings{bergold_et_al:LIPIcs.SWAT.2022.16,
author = {Bergold, Helena and Bertschinger, Daniel and Grelier, Nicolas and Mulzer, Wolfgang and Schnider, Patrick},
title = {{WellSeparation and Hyperplane Transversals in High Dimensions}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {16:116:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16176},
URN = {urn:nbn:de:0030drops161766},
doi = {10.4230/LIPIcs.SWAT.2022.16},
annote = {Keywords: hyperplane transversal, highdimension, hardness}
}
22.06.2022
Keywords: 

hyperplane transversal, highdimension, hardness 
Seminar: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Issue date: 

2022 
Date of publication: 

22.06.2022 