Large \(k\)-gons in a 1.5D Terrain

Given is a 1.5D terrain \(\mathcal{T}\), i.e., an \(x\)-monotone polygonal chain in \(\mathbb{R}^2\). For a given \(2\le k\le n\), our objective is to approximate the largest area or perimeter convex polygon of exactly or at most \(k\) vertices inside \(\mathcal{T}\). For a constant \(k>3\), we d...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-06
Main Author: Keikha, Vahideh
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Polygons
Terrain
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given is a 1.5D terrain \(\mathcal{T}\), i.e., an \(x\)-monotone polygonal chain in \(\mathbb{R}^2\). For a given \(2\le k\le n\), our objective is to approximate the largest area or perimeter convex polygon of exactly or at most \(k\) vertices inside \(\mathcal{T}\). For a constant \(k>3\), we design an FPTAS that efficiently approximates the largest convex polygons with at most \(k\) vertices, within a factor \((1-\epsilon)\). For the case where \(k=2\), we design an \(O(n)\) time exact algorithm for computing the longest line segment in \(\mathcal{T}\), and for \(k=3\), we design an \(O(n \log n)\) time exact algorithm for computing the largest-perimeter triangle that lies within \(\mathcal{T}\).
ISSN:2331-8422