Low crossing paths improve algorithms for set system problems
Low-Crossing Spanning Paths via Quasi-Uniform Sampling and their Applications
Computational GeometryData Structures and Algorithms
Summary
This paper deals with ways to connect points with lines so that these lines cross fewer sets in a given system, which is useful in many areas of computer science. The authors introduce a new method using a sampling technique that speeds up the process for certain types of systems and improves performance guarantees. Their approach leads to faster algorithms for connecting points in patterns that are important in geometry and graph theory. It also offers the first quick method to solve a known problem called combinatorial discrepancy for these systems. Overall, it opens the door to better algorithms in areas where crossing low numbers of sets matters.
What this means in practice
- •For algorithm engineers: Develop faster software for geometric and graph-based problems by constructing spanning paths with fewer crossings in near-linear sized set systems.
- •For optimization specialists: Use the quadratic-time combinatorial discrepancy algorithm to better balance and distribute resources in systems characterized by bounded dual VC-dimension.
Authors
Mónika Csikós, Nabil H Mustafa
Abstract
Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [29, 30] and Chazelle-Welzl [7], who showed that any set system (X, S) with bounded dual VC-dimension d has a matching with crossing number O |X| 1-1/d , which is optimal. Low-crossing matchings and spanning paths have found several applications outside of their initial realm of computational geometry, including algorithmic graph theory, model checking, and game theory. In many of these applications, |S| is near-linear in |X|, which motivated the search for an improved construction for this regime. However, the proposed new algorithms provided only average-case bounds or sub-optimal crossing number guarantees for d $\ge$ 2 [5, 12]. We propose a new quasi-uniform sampling based framework. This allows us to obtain a simple algorithm with expected running time of __ |X| 2 + |S| $\bullet$ |X| , which improves upon the previous-best Our result has several immediate consequences, including new faster algorithms for constructing low-crossing spanning paths for set systems induced by balls, as well as for neighborhood set systems of graphs. Moreover, we get the first quadratic-time algorithm for combinatorial discrepancy, with nearly optimal discrepancy (up to a log factor), for bounded dual VC-dimension set systems. Beyond these applications, we believe that our idea could be applied to other algorithms that use the multiplicative weight update method.