This paper is retracted in Volume-11, Issue-3, 2025
Area
Computational Geometry
Author
Himanshu Kumar Sah
Org/Univ
National Institute of Technology, Durgapur, India
Sub. Date
15 May, 2025
Paper ID
V11I3-1181
Publisher
Keywords
Quadrilateral, Terrain, Inclusion Problem.

Abstract

This paper discusses my understanding, implementation and analysis of various techniques for finding the largest convex quadrilateral inside a terrain. we present a simple new linear time alogrithm for finding the quadrilateral of largest area contained in a convex polygon. A near quadratic time algorithm to locate a largest area convex quadrilateral inside a terrain is presented in this paper.A terrain is a type of simple polygon that is bounded by:- A monotone polygonal chain (usually the upper or lower boundary), and A straight line segment (usually the base or bottom boundary).It is a subclass of simple monotone polygons and is widely studied in GIS(Geographic information system), data modeling, and computational geometry. In this paper we present a novel algorithm to find a largest area of convex quadrilateral inside a terrain with n vertices that run in O(n log2 n) times.