Minimum area circumscribing polygons

DOI10.1007/BF01898354MaRDI QIDQ1822239zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1985

Published in The Visual Computer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01898354

zbMATH Keywords

computational geometryconvex polygongeometric algorithmsoptimization

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25)

Review text

We show that the smallest k-gon circumscribing a convex n-gon can be computed in \(O(n^ 2\log n \log k)\) time.

Recommendations

• Area minimization of special polygons
• The geometry of circumscribing polygons of minimal perimeter
• Circumscribed polygons of small area
• Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition
• Cutting circles and polygons from area-minimizing rectangles
• Minimum-perimeter intersecting polygons
• Minimum-perimeter intersecting polygons
• Minimum area of triangle's circumscribed ellipses
• scientific article; zbMATH DE number 3927286
• The inpolygon with minimal area and the cirenmpolygon

Cites work

• Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition
• Determining the minimum-area encasing rectangle for an arbitrary closed curve
• Finding Extremal Polygons
• Finding the smallest triangles containing a given convex polygon

Cited in

(25)

• Circumscribed polygons of small area
• Geometric applications of a matrix-searching algorithm
• Parallel computational geometry
• Simultaneous inner and outer approximation of shapes
• Stock cutting to minimize cutting length
• Finding minimum area simple pentagons
• An algorithm to find maximum area polygons circumscribed about a convex polygon
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• Finding minimal convex nested polygons
• Approximation of a closed polygon with a minimum number of circular arcs and line segments
• Hausdorff approximation of convex polygons
• Minimum area polygons with two reflex angles enclosingkPoints
• Minimum Area Venn Diagrams Whose Curves Are Polyominoes
• scientific article; zbMATH DE number 5369649 (Why is no real title available?)
• scientific article; zbMATH DE number 5369695 (Why is no real title available?)
• Isoperimetric triangular enclosures with a fixed angle
• The inpolygon with minimal area and the cirenmpolygon
• A hybrid model predictive control scheme for containment and distributed sensing in multi-agent systems
• scientific article; zbMATH DE number 1746653 (Why is no real title available?)
• EFFICIENT APPROXIMATION OF CONVEX POLYGONS
• An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
• scientific article; zbMATH DE number 5025945 (Why is no real title available?)
• The honeycomb conjecture in normed planes and an alpha-convex variant of a theorem of Dowker
• Minimum-perimeter enclosures
• Finding the maximum bounded intersection of k out of n halfplanes

This page was built for publication: Minimum area circumscribing polygons

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