Finding the largest area axis-parallel rectangle in a polygon

DOI10.1016/0925-7721(95)00041-0MaRDI QIDQ676593zbMATH OpenOpenAlexFDO

Authors Karen E. Daniels, Victor J. Milenkovic, Dan Roth

Publication date 4 September 1997

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(95)00041-0

zbMATH Keywords

fast matrix searchinggeometric optimization problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Finding largest rectangles in convex polygons
• Efficient algorithms for the largest rectangle problem
• Maximum-area and maximum-perimeter rectangles in polygons
• scientific article; zbMATH DE number 3883624

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 176589 (Why is no real title available?)
• scientific article; zbMATH DE number 589497 (Why is no real title available?)
• A geometric consistency theorem for a symbolic perturbation scheme
• A polynomial solution for the Potato-peeling problem
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Computing the Largest Empty Rectangle
• Geometric applications of a matrix-searching algorithm
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Medial Axis Transformation of a Planar Shape
• On rectangular visibility
• On the maximum empty rectangle problem
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The orthogonal convex skull problem
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications

Cited in

(23)

• Determining a set of maximum inscribed rectangles for label placement in a region
• Largest area parallelogram inside a digital object in a triangular grid
• Faster algorithms for largest empty rectangles and boxes
• Maximum-area and maximum-perimeter rectangles in polygons
• On Computing a Largest Empty Arbitrarily Oriented Rectangle
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Recognition of largest empty orthoconvex polygon in a point set
• Placing Text Boxes on Graphs
• Finding the largest area rectangle of arbitrary orientation in a closed contour
• An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
• Computing a maximum axis-aligned rectangle in a convex polygon
• Motion smoothing strategies for 2D video stabilization
• Largest unit rectangles inscribed in a convex polygon
• Largest inscribed rectangles in convex polygons
• OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
• Finding largest rectangles in convex polygons
• Finding a largest rectangle inside a digital object and rectangularization
• Finding maximum edge bicliques in convex bipartite graphs
• Large \(k\)-gons in a 1.5D terrain
• Peeling meshed potatoes
• Peeling potatoes near-optimally in near-linear time
• On finding widest empty curved corridors
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon

This page was built for publication: Finding the largest area axis-parallel rectangle in a polygon

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