Next: Optimal Partitioning Up: The Interval Partitioning Problem Previous: Problem Definition

Search Space

Looking at the scenario in figure 5.2, we can see that one major problem of the uniform partition is that its breakpoints go through the interior part of a large number of intervals. In fact, there is no breakpoint which coincides with an interval start- or endpoint. Intuitively, we can move the breakpoints slightly to the left or right to the next point on which one or more `broken' intervals begin or end. This measure possibly reduces but at least does not increase the number of overlaps. This observation suggests that an optimal partition should have its breakpoints within . The remainder of this section shows that this is in fact true. We will even show that optimal partitions can be found within E(R).

Assume that there is an optimal partition $P = \{p_1,$ ..., $p_{m-1}\}$ for some instance of IP. Furthermore assume that P has a breakpoint p_k that is not an endpoint of some interval in R, i.e. . We will show that P can be converted into a partition that has only breakpoints within E(R) and is still optimal in the sense of IP. To that end, breakpoints such as p_k can be moved to the nearest endpoint to the left. See figure 5.4 for an example that shows the benefit of this measure. First, we show that such an endpoint always exists.

Lemma 28659

Let be an instance of IP and with p_k-1 < p_k for an optimal partition according to IP. Then there is always an such that

Proof:

We prove the lemma by contradiction.
Assume that there is an optimal partition P such that there is no with , i.e. no interval ends within the first partition range and thus also intersects with the second one. This means that every interval in the first fragment R₁ - and there must be some because - must also be in the second fragment R₂, i.e.

This means also that

Now, consider the partition . It creates the fragments

with for all . Thus P' satisfies constraint (5.7) of IP. Furthermore we have

Thus P is not optimal in the sense of IP. This contradicts the initial assumption and therefore the lemma holds.

**Figure:** Moving breakpoints to the nearest endpoints to the left in case of the example of figure 5.2.

Now, we will refer to the nearest endpoint to the left of any point t by . It is defined as

Because of lemma 2 this is reduced to

(17)

if p is a breakpoint of an optimal partition.

The next lemma will show how an optimal partition can be subsequently converted into a partition which is (a) optimal for the same instance of IP and (b) consists only of breakpoints that are endpoints of intervals of R. The lemma assumes that the leftmost breakpoint which is not an endpoint is converted first.

Lemma 28693

If there is an instance of IP and a partition

with p_k-1 < p_k for all that satisfies the constraints (5.6) and (5.7) of IP then the partition

for any with also satisfies these constraints.

Proof:

If then

according to (5.9). Thus and the lemma holds.

In the following we assume that and therefore that .
Because of we also know that .

From and the definition (5.9) of we can conclude that

From (5.1) and (5.2) we get

for all t in the domain. But for the t with this works out to be

because of (*). But (**) implies that

with .In particular, i.e. for , this means that

and we can conclude that

But this means that

i.e. that satisfies constraint (5.6).

Now we look at constraint (5.7). Let us refer to the fragments created by P as $R_1, \dots, R_m$ and to those created by as . Trivially, it is

for all and therefore also

for those j as P satisfies (5.7). Thus we need to look at the sizes of the fragments and . These can be derived from the sizes of R_k and R_k+1 in the following way using the lemma 1:

Thus it is . Again, we can conclude later that because otherwise P would not be a minimising partition. Now, we look at the (k+1)-th fragments:

Thus it is . Therefore also satisfies constraint (5.7).

Lemma 3 can now be used to subsequently convert an optimal partition P that has breakpoints that are no interval endpoints into one that is at least as good and that has only breakpoints within E(R). Knowing this, the search for partitions that satisfy the IP-constraints can be restricted to a search within E(R). This is expressed in the following

Theorem 28749

If there is an instance of IP and a partition that satisfies the constraints of IP then there is also a partition that satisfies these constraints.

Proof:

Apply the transformation discussed in lemma 3 subsequently to P until there are no more breakpoints that are not members of E(R). The result is a partition .

The significance of this theorem is that we can now restrict the search for an optimal partition to the set of interval endpoints which is finite:

This also relates the complexity of the problem to the number of intervals and not to the length of the span.

Next: Optimal Partitioning Up: The Interval Partitioning Problem Previous: Problem Definition

Thomas Zurek