Circular clustering with fixed length

Question

Let's say that I have a circular timeline (a 24hr period) with n number of points during these 24hr. I want to cover all points with intervals of a given fixed length k (<24h) and I want to use as few intervals as possible. Is there a good algorithm for determining the start points of the optimal intervals?

If we don't allow intervals to "wrap around" then it becomes easy (we can simply greedily schedule the first interval to start at the first point, cover as many points as possible and pick the next point for the next interval etc.).

A naive quadratic solution would be to try every point as a start point for the "first" interval and do as above but I have a feeling we can do something smarter?

Answer 1

Note about your suggested naive quadratic solution: You'll need to consider each point as either an interval start or an interval end.

---

I'm not sure that this is the optimal solution, but it is better than the naive quadratic:

Let's name the points {P1, ..., Pn}.

Since any point must be covered by at least one interval, find all intervals that may cover point P1 (Assume that an interval either starts at Pi, or ends at Pi). For each of these intervals, continue greedily, as you would on a linear timeline.

To optimize it further, instead of starting with P1, we'll need to find the best start-point - that would be the point that may be covered by the minimal number of intervals. I don't know if we can do this in linear time, but a good heuristic may be to start with the point that the sum of its distances from its two neighbors is maximal.

Edit: An O(nlogn) way for finding the best starting point:

We can build a list of possible 2n segments (for any point Pi an interval may either starts at Pi or ends at Pi). Next, insert these intervals into a segment tree.

Don't use a regular segment tree, but instead of storing the intervals in the canonical subsets, simply store the number of them (See the notes section in Wikipedia's article).

Tree construction would take O(nlogn) time. Now, for each point Pi, count the number of segments (intervals) it falls into. This would take O(logn) for each point, or O(nlogn) total.

Select the point with the minimal number of intervals. For each of the intervals continue with the greedy approach, as described above.

Answer 2

The easy answer is ... constraint programming:

1. you are given a set P of points (say as minutes from midnight) and k the interval length

2. you want the minimal number of intervals (a set S which denote the beginning of the interval) of length k such that

   a. for all p elem P, there exist s in S st p >= s && p <= s+k, in words all given points are 'covered' (if you want it circular just use mod on s+k)

   b. for all S there exist no S' st the number of elements in S' is less than the number of elements in S. in words the result set has minimal cardinality.

Feed it to gecode...and you are done.

There are various possible representations for the intervals, the tradeoffs are nicely explained in K Apt's book 'Principles of Constraint Programming'.