Linear algorithm to find the largest intriangles of a planar convex polygon

DOI10.1108/03684929610124122MaRDI QIDQ4246478zbMATH OpenOpenAlexFDO

Authors Arun K. Pujari, A. Nataraj

Publication date 6 June 1999

Published in Kybernetes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1108/03684929610124122

zbMATH Keywords

computational geometry

Mathematics Subject Classification ID

Length, area, volume and convex sets (aspects of convex geometry) (52A38) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A linear time algorithm for max-min length triangulation of a convex polygon
• A simple linear algorithm for intersecting convex polygons
• A new linear algorithm for intersecting convex polygons
• Algorithm for maximizing a linear function on the set of integral points of a convex polyhedron
• A linear algorithm for determining the separation of convex polyhedra
• A linear time algorithm for finding all farthest neighbors in a convex polygon
• A linear-time approximation scheme for maximum weight triangulation of convex polygons
• A linear algorithm to find a rectangular dual of a planar triangulated graph
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Sequential and parallel algorithms for finding a maximum convex polygon

Cites work

• An Extremal Problem of Geometry
• An optimal algorithm for finding minimal enclosing triangles
• Largest polygons with vertices in a given finite set
• On triangulations of the convex hull of n points
• Solving related two- and three-dimensional linear programming problems in logarithmic time

Cited in

(9)

• Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
• Largest triangle inside a terrain
• Largest triangles in a polygon
• Three problems about simple polygons
• On the most robust affine basis
• scientific article; zbMATH DE number 2169076 (Why is no real title available?)
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• Maximum-area triangle in a convex polygon, revisited
• Finding a largest-area triangle in a terrain in near-linear time

This page was built for publication: Linear algorithm to find the largest intriangles of a planar convex polygon

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