Finding a largest-area triangle in a terrain in near-linear time

DOI10.1007/978-3-030-83508-8_19MaRDI QIDQ832865zbMATH OpenOpenAlexFDO

Authors S. Cabello, Arun Kumar Das, Sandip Das, Joydeep Mukherjee

Publication date 25 March 2022

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

zbMATH Keywords

terraininclusion problemgeometric optimisationhereditary segment tree

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Recommendations

• Largest triangle inside a terrain
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Largest triangles in a polygon
• FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE

Cites work

• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• A polynomial solution for the Potato-peeling problem
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Computational geometry. Algorithms and applications.
• Finding Extremal Polygons
• Finding large sticks and potatoes in polygons
• Finding largest rectangles in convex polygons
• Geometric applications of a matrix-searching algorithm
• Largest triangle inside a terrain
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Maximum-area triangle in a convex polygon, revisited
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• Peeling potatoes near-optimally in near-linear time
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

Cited in

(2)

• FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE
• Large \(k\)-gons in a 1.5D terrain

This page was built for publication: Finding a largest-area triangle in a terrain in near-linear time

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