Largest-Area Convex Quadrilateral in a 1.5D Terrain

2025/11/17 by Ankush Acharyya, Ghosh, Nandana, Nandana Ghosh +2
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Point processes and geometric inequalities #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2511.13209

openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

A 1.5D terrain is a simple polygon bounded by a line segment ℓ and a polygonal chain monotone with respect to the line segment ℓ. Usually, ℓ is chosen aligned to the x-axis, and is called the base of the terrain. In this paper, we consider the problem of finding a convex quadrilateral of largest area inside a 1.5D terrain in ℝ². We present an O(n²) time algorithm for this problem, where n is the number of vertices of the terrain. Finally, we show that the largest area axis-parallel rectangle inside the terrain yields a (1)/(2)-approximation result to the largest convex quadrilateral problem.

Citations

• Dynamic Convex Hulls for Simple Paths
• Large k-gons in a 1.5D Terrain
• Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
• Largest triangles in a polygon
• Dynamic Planar Convex Hull
• Simulation of simplicity: a technique to cope with degenerate cases in\n geometric algorithms

Related

• Large k-gons in a 1.5D Terrain
• Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
• The Largest Contained Quadrilateral and the Smallest Enclosing\n Parallelogram of a Convex Polygon
• Maximum-Area Quadrilateral in a Convex Polygon, Revisited
• Finding Largest Rectangles in Convex Polygons