Finding the largest area axis-parallel rectangle in a polygon

DOI10.1016/0925-7721(95)00041-0zbMath0869.68111OpenAlexW2045509593MaRDI QIDQ676593

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)

Related Items (21)

Maximum-area and maximum-perimeter rectangles in polygons ⋮ Computing a maximum axis-aligned rectangle in a convex polygon ⋮ An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest ⋮ On finding widest empty curved corridors ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ On Computing a Largest Empty Arbitrarily Oriented Rectangle ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Recognition of largest empty orthoconvex polygon in a point set ⋮ Largest area parallelogram inside a digital object in a triangular grid ⋮ Large \(k\)-gons in a 1.5D terrain ⋮ Finding largest rectangles in convex polygons ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ Finding the largest area rectangle of arbitrary orientation in a closed contour ⋮ Largest inscribed rectangles in convex polygons ⋮ Finding a largest rectangle inside a digital object and rectangularization ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Peeling meshed potatoes ⋮ Motion Smoothing Strategies for 2D Video Stabilization ⋮ Placing Text Boxes on Graphs ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ Efficient Algorithm for Computing the Triangle Maximizing the Length of Its Smallest Side Inside a Convex Polygon

Cites Work

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

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