On Thu, Sep 15, 2011 at 7:27 PM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:
I've looked at the patch, and took a brief look at the paper - but I still don't understand the algorithm. I just can't get my head around the concepts of split pairs and left/right groups. Can you explain that in layman's terms? Perhaps an example would help?
In short algorithm works as following:
1) Each box can be projected to the axis as an interval. Box (x1,y1)-(x2,y2) are projected to X axis as (x1,x2) interval and to the Y axis as (y1,y2) interval. At the first step we search for splits of those intervals and select the best one.
2) At the second step produced split are converting into terms of boxes and ambiguities are solving.
Let's see a little deeper how intervals split search are performed by considering an example. We've intervals (0,1), (1,3), (2,3), (2,4). We assume intervals of the groups to be (0,a), (b,4). So, "a" can be some upper bound of interval: {1,3,4}, and "b" can be some lower bound of inteval: {0,1,2}.
We consider following splits: each "a" with greatest possible "b"
(0,1), (1,4)
(0,3), (2,4)
(0,4), (2,4)
and each "b" with least possible "a". In this example splits will be:
(0,1), (0,4)
(0,1), (1,4)
(0,3), (2,4)
By removing the duplicates we've following splits:
(0,1), (0,4)
(0,1), (1,4)
(0,3), (2,4)
(0,4), (2,4)
Proposed algorithm finds following splits by single pass on two arrays: one sorted by lower bound of interval and another sorted by upper bound of interval.
------
With best regards,
Alexander Korotkov.