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

2021/04/23 by Sergio Cabello, Arun Kumar Das, Cabello, Sergio +5 · 1 citation
Computer Science · Engineering · #3D Shape Modeling and Analysis #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2104.11420

openalex publication_date 2021/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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²).

Cited by

• Largest-Area Convex Quadrilateral in a 1.5D Terrain

Related

• Large k-gons in a 1.5D Terrain
• Largest-Area Convex Quadrilateral in a 1.5D Terrain
• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• Largest triangles in a polygon
• Minimum-Area Enclosing Triangle with a Fixed Angle