1
$\begingroup$

I am stuck on that question, it's about Voronoi diagrams

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

In this question, I think the intersections is the vertexes of the farthest site. Am I correct? And I need to prove there is at least $\Omega(n^2)$ intersections like that?

Could you please give me some hint about it?

$\endgroup$
  • $\begingroup$ The question is not clear, what do you mean by "intersection between edges of VD and furthest site"? How can a site have a number of intersections with edges? $\endgroup$ – orezvani May 14 '16 at 16:25
  • $\begingroup$ @emab: Both the Voronoi diagram and the Farthest site Voronoi diagram have edges. You count the intersection points of these. $\endgroup$ – A.Schulz May 14 '16 at 16:30
  • 1
    $\begingroup$ This is the question 7.14 on the famous book: Computational Geometry Algorithms and Applications $\endgroup$ – hminle May 14 '16 at 16:30
  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. It may be helpful if you edited the question to write your thoughts and what you could not figure out. Also, don't forget to attribute your sources! Just copying an exercise from a book without credit is not appropriate. $\endgroup$ – D.W. May 14 '16 at 21:27
  • $\begingroup$ @D.W.: Thank you for your feedback. I will edit my post. But I don't expect the community to solve it, just give me a hint if possible. $\endgroup$ – hminle May 15 '16 at 2:01

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.