Large k-gons in a 1.5D terrain

DOI10.1007/978-3-031-22105-7_5MaRDI QIDQ6168930zbMATH OpenOpenAlexFDO

Authors Vahideh Keikha

Publication date 10 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.02396

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Abstract: Given is a 1.5D terrain $mathcalT$, i.e., an $x$-monotone polygonal chain in $mathbb{R}^2$. For a given $2leklen$, our objective is to approximate the largest area or perimeter convex polygon of exactly or at most $k$ vertices inside $mathcalT$. 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 $mathcalT$, and for $k=3$, we design an $O(nlogn)$ time exact algorithm for computing the largest-perimeter triangle that lies within $mathcalT$.

Recommendations

• scientific article; zbMATH DE number 1098732
• Large cells in Poisson-Delaunay tessellations
• Computing Large Planar Regions in Terrains
• scientific article; zbMATH DE number 761902
• On certain random polygons of large areas
• Large empty convex polygons in \(k\)-convex sets
• Big Polygon Spaces
• Large planar Poisson-Voronoi cells containing a given convex body
• Large triangles in the \(d\)-dimensional unit cube

Cites work

• scientific article; zbMATH DE number 177850 (Why is no real title available?)
• scientific article; zbMATH DE number 1487774 (Why is no real title available?)
• A polynomial solution for the Potato-peeling problem
• An algorithm for generalized point location and its applications
• Finding a largest-area triangle in a terrain in near-linear time
• Finding large sticks and potatoes in polygons
• Finding the largest area axis-parallel rectangle in a polygon
• Largest and smallest convex hulls for imprecise points
• Largest triangle inside a terrain
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• Optimal shortest path queries in a simple polygon
• Peeling potatoes near-optimally in near-linear time

This page was built for publication: Large \(k\)-gons in a 1.5D terrain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168930)