Fixed-length circular clustering

Question

Let's say that I have a circular timeline (24-hour period) with n number of points during these 24 hours. I want to cover all points at 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 starting points of optimal intervals?

If we do not allow the intervals to “wrap around”, then it becomes easy (we can just eagerly plan the first interval to start at the first point, cover as many points as possible and choose the next point for the next interval, etc.).

A naive quadratic solution would be to try each point as a starting point for the “first” interval and do the same as above, but do I have a feeling that we can do something smarter?

Answer 1

Pay attention to the proposed naive quadratic solution: you will need to consider each point as the beginning of an interval or the end of an interval.

---

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

Name the points {P1, ..., Pn}.

Since any point must be covered by at least one interval, find all the intervals that can span the point P1 (suppose that the interval either begins with Pi or ends in Pi). For each of these intervals, continue eagerly, as in the linear timeline.

To optimize it further, instead of starting with P1, we need to find the best starting point - this will be a point that can be covered with a minimum number of intervals. I do not know if we can do this in linear time, but a good heuristic may be to start with the fact that the sum of its distances from its two neighbors is maximum.

Edit: O (nlogn) way to find the best starting point:

We can build a list of possible 2n segments (for any point Pi, the interval can start with Pi or end in Pi). Then insert these intervals into the segment tree.

Do not use a regular segment tree, but instead of storing intervals in canonical subsets, just save their number (see the notes section in the Wikipedia article).

The tree structure will take O (nlogn) time. Now, for each Pi point, count the number of segments (intervals) into which it falls. This will take O (logn) for each point or O (nlogn) total.

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

Answer 2

Easy answer: programming restrictions:

• you are given many points P (for example, minutes from midnight) and k interval length

• you need the minimum number of intervals (the set S denoting the beginning of the interval) of length k such that

  but. for all p elem P there are s in S st p> = s && p <= s + k, in words all the indicated points are “covered” (if you want the circles to use mod on s + k)

  b. for all S there is no S ', the number of elements in S' is less than the number of elements from S. in words, as a result, the set of results has minimal power.

Download it in gecode ... and you're done.

There are various possible representations for intervals; trade-offs are well explained in K Apt's book, Principles of Programming Constraints.

Answer 3

Perhaps you can use a space curve and a four-key hierarchical cluster. There is a French site organizing days along the gap filling curve: http://lapin-bleu.net/riviera/?p=78 . But what is probem with a quadratic algorithm?