Well-Separation and Hyperplane Transversals in High Dimensions
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Well-Separation and Hyperplane Transversals
Forlagets udgivne version, 747 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 |
Redaktører | Artur Czumaj, Qin Xin |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2022 |
Sider | 1-14 |
Artikelnummer | 16 |
ISBN (Elektronisk) | 9783959772365 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 - Torshavn, Færøerne Varighed: 27 jun. 2022 → 29 jun. 2022 |
Konference
Konference | 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 |
---|---|
Land | Færøerne |
By | Torshavn |
Periode | 27/06/2022 → 29/06/2022 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 227 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Helena Bergold: Supported by the German Science Foundation within the research training group “Facets of Complexity” (GRK 2434). Nicolas Grelier: Supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681. Wolfgang Mulzer: Supported in part by ERC StG 757609 and by the German Research Foundation within the collaborative DACH project Arrangements and Drawings as DFG Project MU 3501/3-1.
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
ID: 314447272