# Ω($n^2$) intersections between the edges of the Voronoi diagram and the farthest site Voronoi diagram.

I'm working through Mark DeBerg's Computational Geometry book and I'm stuck on question 7.16 which states the following:

Show that for some set P of n points, there can be Ω($n^2$) intersections between the edges of the Voronoi diagram and the farthest site Voronoi diagram.

A point p in a point set P has a cell in the farthest-point Voronoi diagram iff it is on the convex hull of P. Then to answer the question above, for there to be $n^2$ intersections, would a point set in which all points lie on the convex hull be a solution?

Thanks!

• I have been working on these issues some time ago. I would try a double family of points that I express under complex form: $e^{2ik\pi/n}$ and $Re^{2i(k+0.5)\pi/n}$ with $R=1+\varepsilon$ for $k=1,\cdots n$. Remark: In a funny way, in this, one of the answers direct to this books' exercise! – Jean Marie Nov 6 '16 at 0:45
• ... maybe with $\varepsilon$ such that the convex hull of the first set of points (which is a regular polygon) is inscribed in the convex hull of the second set of points (a regular polygon too) due to the shift $k \rightarrow k+1/2$. – Jean Marie Nov 6 '16 at 0:49