Seminar: Crossing and Independent Families among Polygons

Speaker: Anna Brötzner, Department of Computer Science and Media Technology, Malmö University

Title: Crossing and Independent Families among Polygons

Abstract: Given a set A of points in the plane, a family of line segments forming a matching in A is called crossing (or independent) if each pair of segments in the family intersects (or is non-intersecting, respectively). In past works, these notions have been generalized to polygons by identifying the points in A with the vertices of a given set of polygons and forbidding the line segments from intersecting or overlapping with polygon walls. In this work, we study the computational complexity of computing maximum crossing and independent families in this more general setting. We show that both problems are NP-hard already when the polygons are triangles. Motivated by this, we turn to parameterized algorithms. We consider the number of polygons on the input as the natural parameter and under this parameterization obtain a fixed-parameter algorithm for computing a largest crossing family among these polygons, and a separate XP-algorithm for computing a largest independent family that lies in one of the faces of the polygonal domain.

This talk is based on joint work with Robert Ganian, Thekla Hamm, Fabian Klute, and Irene Parada, and will also be presented at WADS'25.