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?


  • $\begingroup$ 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! $\endgroup$ – Jean Marie Nov 6 '16 at 0:45
  • $\begingroup$ ... 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$. $\endgroup$ – Jean Marie Nov 6 '16 at 0:49

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.