Faster ways to find independent triples in overlapping disk groups

Computing Independent Sets of Size Three in Disk Graphs

Computational GeometryData Structures and Algorithms

Summary

Finding three disks that don’t overlap in a group of disks placed on a flat surface can be slow if done by checking every combination. The authors found a faster way to find such groups of three disks that don’t touch by using clever math and geometry ideas. They make the problem quicker to solve, especially when disks or their centers form certain shapes called convex arrangements. This work shows even small problems like groups of three have interesting patterns and can be solved efficiently.

What this means in practice

  • For geospatial analysts: Identify non-overlapping groupings of sensing regions faster in spatial data visualizations and sensor network designs.
  • For network planners: Optimize layout planning by quickly finding independent sets of coverage areas in wireless or cellular network designs.

Authors

Anastasiia Tkachenko, Haitao Wang

Abstract

We study the problem of computing an independent set of size three in disk graphs, where vertices correspond to disks in the plane and two vertices are adjacent if their disks intersect. While computing a maximum independent set in disk graphs is NP-hard, the fixed-size case admits more efficient solutions. Given a set of $n$ disks, we present an algorithm to compute an independent set of size three in the disk graph and our algorithm runs in randomized expected $O^*(n^{5/3})$ time, where $O^*$ hides a factor of $n^ε$ for an arbitrarily small $ε> 0$. Our approach introduces a framework based on semi-algebraic range searching and tree-structured biclique partitions, which allows us to group pairs of disjoint disks into canonical subsets and avoid redundant computations. When the centers of the disks are in convex position, we solve the problem in $O(n \log^2 n)$ deterministic time. We also consider the case in which the disks themselves are in convex position, i.e., each disk contributes to the boundary of the convex hull of all disks, and obtain an $O(n \log^2 n)$ time algorithm for this setting as well. Our techniques for these cases are based on geometric properties of disk arrangements. In particular, they rely on new structural lemmas that reduce the problem to efficiently testing certain ordered configurations of disks. Our results improve upon the straightforward quadratic time approach and demonstrate how geometric structures and range searching techniques can be leveraged to solve fixed-size independent set problems in disk graphs more efficiently. To the best of our knowledge, this is the first systematic study of independent sets of size three in disk graphs. Our results show that even this smallest nontrivial case exhibits rich structural properties, especially under convexity assumptions.