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

Improve this question
$\endgroup$
2
  • $\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
    Commented May 28, 2018 at 21:22
  • $\begingroup$ @Jake I've added a clarification for triangulation in the question. $\endgroup$
    – Chypsylon
    Commented May 29, 2018 at 6:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't you mean in time $o(n\log n)$ ? $\endgroup$
    – user16034
    Commented May 29, 2018 at 9:25
  • $\begingroup$ @YvesDaoust, oops, you are right. Thanks. Corrected. $\endgroup$
    – D.W. ♦
    Commented May 29, 2018 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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