Re: Need efficient search strategy in list of time intervals

lemmi wrote:
Hi,

I was wondering if someone of you could help me out with an
algorithmic problem I have. This is not a homework exercise but
something I need for a UI framework that I have developed
(www.dlsc.com).

I have a list of time intervals ([long,long]). The list is sorted
based on the start times of the intervals. I now need a fast
algorithm, which takes a time span TS as input and returns the index
of the first time interval A in the list that is contained in the
given time span. The rendering engine of my UI framework will then
iterate over the list starting at the calculated index.

A time interval A is "contained" when A does not end before TS begins
and also does not start after TS ends (!(A.end < TS.start || A.start >
TS.end).

The algorithm gets constantly called as part of a paint() method so it
needs to be extremely fast (linear is not good enough, logarithmic
would be ideal).

To make things complicated. The intervals can overlap each other. An
interval A that starts earlier than B might very well end after B.
A.start < B.start && A.end > B.end.

Note: a standard binary search does not work because it might find a
time interval that ends before the input time span TS and then
interrupts its search even though another time interval is located
before it that ends after it.

Dirk


Does the start time of the probe interval ever reduce? If not, consider
the following:

Keep the intervals in a doubly linked list, such as
java.util.LinkedList, sorted in ascending order of start time.

For each search, scan the list from the start.

If the start time is greater than the probe end time, stop. You have
found all the overlaps for this probe.

Else if the end time is less than the probe start time, delete the interval.

Any interval that passes both those tests overlaps the probe. Each
interval is operated on at most once after it becomes irrelevant, and
otherwise you only look at one non-hit.

The harder problem is if the interface start time can reduce. If so,
perhaps you should think of your intervals as points in a two
dimensional space, indexed by start and end time. The probe interval is
a rectangular region of that space. Look at R-tree, KD-tree etc. to see
if there is something that helps.

Patricia

.

Relevant Pages

  • Re: nearest colour and thanks for the palette help
    ... Theoretically you will get your algorithm run 16 times faster than iterating palette searching for minimum, practically, since jumping trough pointers is slower than iterating a table, it would be say about 8 times faster. ... If there is an 'n' here at all, it's the number of PROBE points. ...
    (comp.graphics.algorithms)
  • Re: JSH: Not obvious? Simple math test.
    ... then you have the skills to program the ... algorithm I posted for yourself. ... I count 1 "probe" for every GCD that ...
    (sci.crypt)