Well-Separation and Hyperplane Transversals in High Dimensions
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Well-Separation and Hyperplane Transversals in High Dimensions. / Bergold, Helena; Bertschinger, Daniel; Grelier, Nicolas; Mulzer, Wolfgang; Schnider, Patrick.
18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022. red. / Artur Czumaj; Qin Xin. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. s. 1-14 16 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 227).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Well-Separation and Hyperplane Transversals in High Dimensions
AU - Bergold, Helena
AU - Bertschinger, Daniel
AU - Grelier, Nicolas
AU - Mulzer, Wolfgang
AU - Schnider, Patrick
N1 - Publisher Copyright: © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - hardness
KW - high-dimension
KW - hyperplane transversal
UR - http://www.scopus.com/inward/record.url?scp=85133403562&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2022.16
DO - 10.4230/LIPIcs.SWAT.2022.16
M3 - Article in proceedings
AN - SCOPUS:85133403562
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 14
BT - 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022
A2 - Czumaj, Artur
A2 - Xin, Qin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022
Y2 - 27 June 2022 through 29 June 2022
ER -
ID: 314447272