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