2
$\begingroup$

How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$?

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \log n)$. Is it valid to argue that since the convex hull is also part of the triangulation it can't be done faster or else the lower bound for the hull would also be lower?

Edit: By Triangulation I mean connecting all the points via non-crossing edges such that they form triangles: https://en.wikipedia.org/wiki/Point_set_triangulation

$\endgroup$
  • $\begingroup$ To argue via the connection between them you'd have to argue that you could compute the convex hull faster than that if you had a faster algorithm to compute triangulation. Also, can you define what you mean by "getting a triangulation" others might be familiar with this term but I am not. $\endgroup$ – Jake May 28 '18 at 21:22
  • $\begingroup$ @Jake I've added a clarification for triangulation in the question. $\endgroup$ – Chypsylon May 29 '18 at 6:53
2
$\begingroup$

No, that's not a valid argument. You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.

$\endgroup$
  • $\begingroup$ Don't you mean in time $o(n\log n)$ ? $\endgroup$ – Yves Daoust May 29 '18 at 9:25
  • $\begingroup$ @YvesDaoust, oops, you are right. Thanks. Corrected. $\endgroup$ – D.W. May 29 '18 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.