SCHEDULING DYADIC INTERVALS

We consider the problem of computing the shortest schedule of the inte rvals [j2(-i), (j + 1)2(-i)), for O less than or equal to j less than or equal to 2(i) - 1 and 1 less than or equal to i less than or equal to k such that separation of intersecting intervals is at least R. Thi s problem arises in an application of wavelets to medical imaging. It is a generalization of the graph separation problem for the intersecti on graph of the intervals, which is to assign the numbers 1 to 2(k+1) - 2 to the vertices, other than the root, of a complete binary tree of height k in such a way as to maximize the minimum difference between all ancestor descendent pairs. We give an efficient algorithm to const ruct optimal schedules.