Skip to main content
Computer Science

Return to Question

Clarified Triangulation
Source Link
Chypsylon
Chypsylon
  • 23
  • 3

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

How can I show that the lower bound for getting a triangulation from a point set 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?

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

deleted 12 characters in body
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \cdot log(n))$$\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?

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

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \cdot 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?

How can I show that the lower bound for getting a triangulation from a point set 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?

Source Link
Chypsylon
Chypsylon
  • 23
  • 3

Lower bound for point set triangulation

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

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \cdot 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?