Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.13209 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908830896488448 |
|---|---|
| author | Ghosh, Nandana Gupta, Rakesh Acharyya, Ankush |
| author_facet | Ghosh, Nandana Gupta, Rakesh Acharyya, Ankush |
| contents | A $1.5$D terrain is a simple polygon bounded by a line segment $\ell$ and a polygonal chain monotone with respect to the line segment $\ell$. Usually, $\ell$ 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.5$D terrain in $\mathbb{R}^2$. We present an $O(n^2)$ 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 $\frac{1}{2}$-approximation result to the largest convex quadrilateral problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13209 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | In search of the Giant Convex Quadrilateral hidden in the Mountains Ghosh, Nandana Gupta, Rakesh Acharyya, Ankush Computational Geometry A $1.5$D terrain is a simple polygon bounded by a line segment $\ell$ and a polygonal chain monotone with respect to the line segment $\ell$. Usually, $\ell$ 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.5$D terrain in $\mathbb{R}^2$. We present an $O(n^2)$ 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 $\frac{1}{2}$-approximation result to the largest convex quadrilateral problem. |
| title | In search of the Giant Convex Quadrilateral hidden in the Mountains |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2511.13209 |