6
$\begingroup$

I'm trying to implement the Fortune's Algorithm, however I can't quite figure out how the status structure should be implemented. The following is extrapolated from my Computational Geometry book.

The beach line is represented by a balanced binary search tree $\mathcal{T}$; it is the status structure. Its leaves corresponds to the arcs of the beach line. Which is $x$-monotone-in an ordered manner: the leftmost leaf represents the leftmost arch, the next leaf represents the second leftmost arc, and so on. Each leaf $\mu$ stores the site that defines the arc it represents. The internal nodes of $\mathcal{T}$ represents the break points on the beach line. A break point is stored at an internal node by an ordered tuple of sites $\langle p_i,p_j\rangle$ where $p_i$ defines the parabola at the left breakpoint and $p_j$ defines the parabola to the right. Using this representation of the beach line, we can find in $O(\log n)$ time the arc of the beach line lying above a new site. At an internal node we simply compare the $x$-coordinate of the new site with the $x$-coordinate of the breakpoint, which can be computed from the tuple of sites and the position of the sweep line in constant time. Note that we do not explicitly store the parabolas.

In $\mathcal{T}$ we also store pointers to the other two data structures using the sweep. Each leaf of $\mathcal{T}$, representing an arc $\alpha$, stores one pointer to a node in the event queue, namely, the node that represents the circle event in which $\alpha$ will disappear. This pointer is nil if no circle event exists where $\alpha$ will disappear, or this circle event hasn't be detected yet. Finally every internal node $\nu$ has a pointer to a half-edge in the double-connected edge list of the Voronoi diagram. More precisely, $\nu$ has a pointer to one of the half-edges of the edge being traced out by the breakpoint represented by $\nu$.

By reading through the description I'm not entirely sure how this $\mathcal{T}$ should be implemented. What I know about balanced search trees comes from basic courses in algorithm design, one instance instance is red-black tree. However say I have such red black tree (with some order criteria), whose node's data are both points $p_i$ or pairs $\langle p_i,p_j \rangle$, say I'm adding a new node to such tree, a new site $p_k$ for example. Assume that inserting $p_k$ will result in violating one of the RB-tree properties, I might need to perform a rotation and maybe such a rotation could bring one of the pairs $\langle p_i,p_j \rangle$ to be one of the leaves, or maybe a site could become an internal node. Now I have two questions

  1. How do I guarantee that during balancing operations the invariant? namely pairs are internal node, and leaves are sites?
  2. What criteria should I use to compare for example break points respect to sites point?

For an actual implementation maybe I should just store points in the tree, labeling somehow them to describe what they actually are, and among the fields I should probably add pointers to sites in order to understand of which arcs a point $p$ represents the breakpoints. Also...

It seems to me the the event queue $\mathcal{Q}$ has two kinds of events, site events and circle events. If I had a fibonacci heap described as in CLRS book I can only access to the min node. I can never access to internal nodes, however from the description above I need to retrieve sometimes these events from the event queue, and eventually remove them, doesn't this some how affect the computational complexity (time) of the whole algorithm?

Update:

I'm not neither sure the properties can be maintained at each iteration of the algorithm. Take the following example, assume you have two sites, first site $p_1$ the second site $p_2$ below $p_1$. When $p_1$ is met then only this site is inserted in $\mathcal{T}$, when the second site is met $p_1$ is removed and the tree should store $p_2$,$\langle p_1,p_2 \rangle$ and $\langle p_2,p_1 \rangle$. Sorting these three will imply $\langle p_1,p_2 \rangle \le p_2 \le \langle p_2,p_1 \rangle$, and no binary search tree can maintain the properties mentioned, at least one pair is going to be a leaf. The only acceptable case would be a list where $p_2$ is the leaf, but this is a contradiction.

Update 2 :

The boost library seems providing an implementation. Reading through the code, hoping I'll understand the implementation of the beach line part.

Update 3 :

I haven't touched the subject in a while but I had some thoughts later, but I'll write them down so eventually someone can confirm me whether or not I'm right or still I'm missing something. First of all let $s_1,\dots, s_n$ the parabola segments from left to right, let $l_y$ be the sweep line below those segments, where $y$ is the coordinate of the sweep line, but above the next event point $p$. For each $y$ meeting such condition we define $I_{1,y},\ldots, I_{n,y}$ as the collection of segments obtained by projecting $s_1,\ldots, s_n$ into the sweep line, such intervals are disjoint, and we can easily retrieve the corresponding parabola given such segment (therefore there's a bijection between $s_i$ and $I_{i,y}$). For each $1 \leq i \leq n$ we have

$$ I_{i,y} = [a_y,b_y] $$

This means that the beach line can be represented using a balanced binary search tree, with keys the intervals $I_{i,y}$ and with values the sites $p_i$. Therefore is going to be something like

class MyCmp {
 public:
   ...
 private:
   float y; //sweep line coord
};

while the actual structure will be something like

std::map<Interval,Site,MyCmp> beach_line(...);

When we want to insert a new site, $p_{n+1}$ will have the interval $I_{n+1,y} = [p_{n+1}.x,p_{n+1}.x]$ therefore we just retrieve the interval $I_{k,y}$ that contains it, we remove such interval, we split the interval in three $I_{k,y}^-,I_{n+1,y},I_{k,y}^+$ and we insert these three in the tree, creating also new candidates for circle events to be inserted in the priority queue.

Basically the idea would be: 1. Develop from scratch an interval tree 2. Reuse the std::map container to represent an interval tree, actually an augmented one because of the y coordinate.

$\endgroup$
  • $\begingroup$ there seem to be several different questions here, eg (1) how the highly optimized Fortune algorithm works with specialized datastructures (2) how red black tree dynamics works. suggest you try to figure out which is the particular focus... it is possible to implement Fortune algorithm with similar datastructures some more optimized than others. $\endgroup$ – vzn Sep 11 '17 at 22:59
  • $\begingroup$ How could you get I was asking about red black trees? I was observing that if you had a red black tree as status structure you cannot maintain sites at the leaves and pairs at internal points... You said that it can be implemented in several ways... I'm still waiting for a complete answer explaining in detail how it is fully implemented. The boost library is the only reference in such sense I managed to find. $\endgroup$ – user8469759 Sep 12 '17 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.