An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest

DOI10.1137/22M1482676MaRDI QIDQ5056924zbMATH OpenFDO

Authors Rubén Molano, Mar Ávila, José Carlos Sancho, Pablo G. Rodríguez, Andrés Caro

Publication date 8 December 2022

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

zbMATH Keywords

areaperimetersimple polygonregion of interest\(k\)-gon

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10) Length, area, volume and convex sets (aspects of convex geometry) (52A38)

Recommendations

• An algorithm to find maximum area polygons circumscribed about a convex polygon
• A note on lower bounds for the maximum area and maximum perimeter k-gon problems
• Algorithms for optimal area triangulations of a convex polygon
• scientific article; zbMATH DE number 2169076
• scientific article; zbMATH DE number 1416198
• On maximum area polygons in a planar point set
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• Computing area-optimal simple polygonizations
• scientific article; zbMATH DE number 742951
• Maximum-area and maximum-perimeter rectangles in polygons

Cites work

• scientific article; zbMATH DE number 3907805 (Why is no real title available?)
• A polynomial solution for the Potato-peeling problem
• An optimal algorithm for finding minimal enclosing triangles
• Determining the minimum-area encasing rectangle for an arbitrary closed curve
• Fareys series and Pick's area theorem
• Finding Extremal Polygons
• Finding a largest rectangle inside a digital object and rectangularization
• Finding large sticks and potatoes in polygons
• Finding the largest area axis-parallel rectangle in a polygon
• Finding the largest area rectangle of arbitrary orientation in a closed contour
• Finding the smallest triangles containing a given convex polygon
• Geometric applications of a matrix-searching algorithm
• Introduction to algorithms.
• Largest inscribed rectangles in convex polygons
• Maximum-area triangle in a convex polygon, revisited
• Minimum area circumscribing polygons
• Minimum-perimeter enclosures
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• On the minimum perimeter triangle enclosing a convex polygon
• Polygon Area Decomposition for Multiple-Robot Workspace Division
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• The simple grid polygon exploration problem

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest

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