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

370 Views Asked by At

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!