20.500.12556/DiRROS-21677 Finding a largest-area triangle in a terrain in near-linear time 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)$. terrain inclusion problem geometric optimisation hereditary segment tree true false true Angleški jezik Ni določen Neznano 2025-03-12 10:30:26 2025-03-12 10:30:26 2025-03-13 03:52:38 0000-00-00 00:00:00 2025 0 0 13 str. [article no.] 102171 Vol. 128 Sep. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-09-01 004.92:519.8 0925-7721 10.1016/j.comgeo.2025.102171 228678147 1-s2.0-S0925772125000094-main.pdf 1-s2.0-S0925772125000094-main.pdf 1 8B8DC292CEF31313DF64E5F9E473542D 2169b85e7b54a7fdacf550eb400b8ec3966733e09ecc55d185dfa125c2e8a21a d3f6f7da-ff24-11ef-88ed-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=31074 https://www.sciencedirect.com/science/article/pii/S0925772125000094 1 a27ce937-ff24-11ef-88ed-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=31073 Inštitut za matematiko, fiziko in mehaniko 0 0 0