Finding a largest-area triangle in a terrain in near-linear timeCabello, Sergio (Avtor) Das, Arun Kumar (Avtor) Das, Sandip (Avtor) Mukherjee, Joydeep (Avtor) terraininclusion problemgeometric optimisationhereditary segment treeA 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)$.20252025-03-12 10:30:26Neznano21677sl