Well-Separation and Hyperplane Transversals in High Dimensions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Well-Separation and Hyperplane Transversals
Final published version, 747 KB, PDF document
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 Rd, 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 Rd, 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 Rd, it turns out that checking whether there is a (d -1)-transversal is W[1]-hard with respect to d.
Original language | English |
---|---|
Title of host publication | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 |
Editors | Artur Czumaj, Qin Xin |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2022 |
Pages | 1-14 |
Article number | 16 |
ISBN (Electronic) | 9783959772365 |
DOIs | |
Publication status | Published - 2022 |
Event | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 - Torshavn, Faroe Islands Duration: 27 Jun 2022 → 29 Jun 2022 |
Conference
Conference | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 |
---|---|
Land | Faroe Islands |
By | Torshavn |
Periode | 27/06/2022 → 29/06/2022 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 227 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
- hardness, high-dimension, hyperplane transversal
Research areas
ID: 314447272