I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly written wordpress site with a cool tool: But I am not finding any well written text explaining and proving an algorithm to get the voronoi diagram, keyword being proving.

It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{DG}(P)$. A Gabriel graph is defined as: The Gabriel graph $\mathcal{GG}(P)$ of a point set $P \subset \mathbb{R}^2$ is defined as follows. The vertex set is $P$ and two vertices $p, q$ in $P$ are connected by an edge if and only if the interior of the disk with diameter $\overline{pq}$ is empty and $p, q$ are the only two points on its boundary. In particular, this implies that $\overline{pq}$ is also an edge in the Delaunay graph of P. However, I am struggling to visualize or understand in what cases an edge $(p, q)$ would be in $\mathcal{DG}(P)$ but not in $\mathcal{GG}(P)$. Could someone give me an example? It seems to me as, by the empty-circle property of Voronoi edges, and their duality with the Delaunay graph, every edge in the Delaunay graph should satisfy the definition of a Gabriel graph. It is obvious that I am missing some edge case.

I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays. Similarly how can we draw the Voronoi diagram for the following: (a) A set of lines and points? (b) A set of disjoint line segments? (c) A set of line segments forming a convex polygon? (d) A set of circles (non intersecting and no circle contains another)? For each of these sets of objects, how can we describe the shape of the boundary pieces that form the Voronoi diagram. I believe that the distance between a point and another object is the smallest distance between the point and any point of the object.

Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x and V(y) be the Voronoi cell of y. Prove or disprove that V(x) and V(y) share an edge in Vor(P ). Here,as per my understanding, the shortest edge xy means that no other edge with one red endpoint and one blue endpoint is shorter. However, there may be edges with both red endpoints or both blue endpoints that are much shorter.