An optimal algorithm for finding minimal enclosing triangles

DOI10.1016/0196-6774(86)90007-6zbMath0606.68038OpenAlexW2040178277MaRDI QIDQ3745275

Alok Aggarwal, Joseph O'Rourke, Sanjeev R. Maddila, Michael Baldwin

Publication date: 1986

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(86)90007-6

zbMATH Keywords

convex polygonminimal area triangles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx)

Related Items (39)

A polynomial solution for the Potato-peeling problem ⋮ Finding minimal enclosing boxes ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Largest \(j\)-simplices in \(n\)-polytopes ⋮ An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest ⋮ A B-spline basis for \(C^1\) quadratic splines on triangulations with a 10-split ⋮ Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance ⋮ AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER∗ ⋮ Parallel computational geometry ⋮ Isoperimetric triangular enclosures with a fixed angle ⋮ Perspectives of Monge properties in optimization ⋮ Optimizing Squares Covering a Set of Points ⋮ Minimum-width rectangular annulus ⋮ Minimum-area enclosing triangle with a fixed angle ⋮ Construction and analysis of cubic Powell-Sabin B-splines ⋮ Stretch‐induced wrinkling analysis of thin sheets with splines ⋮ Separating Bichromatic Point Sets by Minimal Triangles with a Fixed Angle ⋮ Polynomial-time approximation of largest simplices in \(V\)-polytopes. ⋮ QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS ⋮ An algorithm to find maximum area polygons circumscribed about a convex polygon ⋮ \(\mathcal{C}^1\) cubic splines on Powell-Sabin triangulations ⋮ Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares ⋮ Minimum Width Rectangular Annulus ⋮ A stabilized Powell-Sabin finite-element method for the 2D Euler equations in supersonic regime ⋮ Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet ⋮ Optimizing squares covering a set of points ⋮ Translating a convex polygon to contain a maximum number of points. ⋮ TURNING SHAPE DECISION PROBLEMS INTO MEASURES ⋮ Implementation of linear minimum area enclosing triangle algorithm. Application note ⋮ Finding the maximum bounded intersection of \(k\) out of \(n\) halfplanes ⋮ The use of Powell-Sabin B-splines in a higher-order phase-field model for crack kinking ⋮ Approximation of convex sets by polytopes ⋮ Optimal placement of convex polygons to maximize point containment ⋮ Computing shortest transversals ⋮ Extremal convex polygons inscribed in a given convex polygon ⋮ Finding minimal convex nested polygons ⋮ Toward Quantifying Vertex Similarity in Networks ⋮ EFFICIENT APPROXIMATION OF CONVEX POLYGONS ⋮ Linear algorithm to find the largest intriangles of a planar convex polygon

This page was built for publication: An optimal algorithm for finding minimal enclosing triangles