Finding a Largest-Area Triangle in a Terrain in Near-Linear Time

04/23/2021
by   Sergio Cabello, et al.
0

A terrain is an x-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in O(n log n) time, where n is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of O(n^2).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset