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 -