Finding the smallest triangles containing a given convex polygon

DOI10.1016/0196-6774(85)90005-7MaRDI QIDQ3697817zbMATH OpenOpenAlexFDO

Authors Victor Klee, M. C. Laskowski

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0196-6774(85)90005-7

zbMATH Keywords

anchored triangleconvex polygonHausdorff distancelocal minimumpolynomial algorithmtriangles of minimum area

Mathematics Subject Classification ID

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)

Recommendations

• Finding minimal convex nested polygons
• scientific article; zbMATH DE number 2123350
• The complexity of finding small triangulations of convex 3-polytopes
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• On the minimum perimeter triangle enclosing a convex polygon
• scientific article; zbMATH DE number 522850
• An optimal algorithm for finding minimal enclosing triangles
• Finding minimal nested polygons
• Computing the Smallest T-Shaped Polygon Containing k Points
• Finding small triangulations of polytope boundaries is hard

Cited in

(35)

• A polynomial solution for the Potato-peeling problem
• Parallel computational geometry
• Minimum vertex hulls for polyhedral domains
• Optimal placement of convex polygons to maximize point containment
• On the complexity of some basic problems in computational convexity. I. Containment problems
• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• A B-spline basis for C^1 quadratic splines on triangulations with a 10-split
• Construction and analysis of cubic Powell-Sabin B-splines
• An algorithm to find maximum area polygons circumscribed about a convex polygon
• A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane
• Optimizing squares covering a set of points
• The Santalo point of a planar convex set
• Minimum area circumscribing polygons
• Finding minimal convex nested polygons
• Largest \(j\)-simplices in \(n\)-polytopes
• Implementation of linear minimum area enclosing triangle algorithm. Application note
• Using symbolic calculations to determine largest small polygons
• Extremal convex polygons inscribed in a given convex polygon
• Translating a convex polygon to contain a maximum number of points.
• Approximation of convex sets by polytopes
• Optimizing squares covering a set of points
• ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS
• Finding minimal enclosing boxes
• An optimal algorithm for finding minimal enclosing triangles
• Minimum-area enclosing triangle with a fixed angle
• EFFICIENT APPROXIMATION OF CONVEX POLYGONS
• AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER∗
• An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
• Three convex hull theorems on triangles and circles
• Separating bichromatic point sets by minimal triangles with a fixed angle
• Minimal convex \(k\)-gons containing a given convex polygon
• \(\mathcal{C}^1\) cubic splines on Powell-Sabin triangulations
• Computing shortest transversals
• Finding the maximum bounded intersection of k out of n halfplanes

This page was built for publication: Finding the smallest triangles containing a given convex polygon

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