2026-07-23T14:53:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16176 2024-03-06T10:57:05Z ddc:004 open_access

Well-Separation and Hyperplane Transversals in High Dimensions Bergold, Helena Bertschinger, Daniel Grelier, Nicolas Mulzer, Wolfgang Schnider, Patrick hyperplane transversal high-dimension hardness A family of k point sets in d dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong assumption that allows us to conclude that certain kinds of generalized ham-sandwich cuts for the point sets exist. But how hard is it to check if a given family of high-dimensional point sets has this property? Starting from this question, we study several algorithmic aspects of the existence of transversals and separations in high-dimensions. First, we give an explicit proof that k point sets are well-separated 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 well-separation lies in the complexity class coNP. Next, we show that it is NP-hard to decide whether there is a hyperplane-transversal (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 well-separation is coNP-complete. Furthermore, we show that finding a hyperplane that maximizes the number of intersected sets is NP-hard, 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 NP-complete. 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 (k-2)-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 (d-1)-transversal is W[1]-hard with respect to d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Helena Bergold and Daniel Bertschinger and Nicolas Grelier and Wolfgang Mulzer and Patrick Schnider 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.16 urn:nbn:de:0030-drops-161766 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode