Shooting balloons and problems on circular arcs

The Fall 1999 UIUC theory qual has a problem on shooting balloons. There are $n$ balloons (disks) on the plane, and you are standing at a given point. Find the minimum number rays to shoot so you can pop all the balloons.

It reminds me of the interval version of the problem.

Problem1

There are $n$ interval on the real line, find minimum number of points on the line such that every interval contains at least one of the points.

There is a common $O (n lo g n)$ algorithm where the time is dominated by sorting. Pick the left most right end point of the uncovered intervals until all intervals are covered.

Almost all interval related problem can be generalized to circular arcs. There are a certain set of problems on circular arcs that seems quite easy to solve. Wlog, assume no circular arc completely contain another.

Problem2

There are $n$ arcs on the unit circle, find minimum number of points on the circle such that every arc contains at least one of the points.

We can use $O (n lo g n)$ time to sort. Break the circle at the start of some arc and consider the real line version of the problem. Total of $O (n^{2})$ time because there are $n$ possible starting positions.

However, one can show any starting arc can get you the same solution, and use the same algorithm as the interval version! In fact, this idea works for a few other problems too, include maximum independent set of arcs. [1]

For interval graphs, if it is hard to come up with a combinatorial algorithm, one based on LP might still work. The interval graph induces a totally unimodular matrix. For example, find a maximum weight independent set on a interval graph can be solved with dynamic programming, but what about finding a maximum weight set where we allow each arc to intersect at most $k$ times? [2]

For proper circular arc graphs, the adjacency matrix is not totally unimodular, however, it is nearly totally unimodular, which has nice properties like totally unimodular matrices. One particularly interesting problem is the following. An arc is an $α$ -arc, if the arc length of the arc is at most $α$ . Given a set of points on the circle, one is interested in finding a covering using disjoint set of $α$ -arcs. The problem was conjectured to be NP-hard, but one can devise a combinatorial algorithm using nearly totally unimodular formulation [Gijswijt05].

References

[1]

W. Hsu, K. Tsai, Linear time algorithms on circular-arc graphs, Information Processing Letters. 40 (1991) 123–129.

[2]

P. Winkler, L. Zhang, Wavelength assignment and generalized interval graph coloring, in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial; Applied Mathematics, Philadelphia, PA, USA, 2003: pp. 830–831.

Posted by Chao Xu on 2014-08-20.

Tags: Algorithm.