scientific article; zbMATH DE number 7205030

DOI10.4230/LIPICS.ESA.2017.52zbMATH Open1442.68252MaRDI QIDQ5111741FDOQ5111741

Authors Haim Kaplan, Sasanka Roy, Micha Sharir 

Publication date 27 May 2020

zbMATH Keywords

areacomputational geometrygeometric optimizationperimeterrectangles

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Length, area and volume in real or complex geometry (51M25)

Recommendations

• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• Finding the largest area axis-parallel rectangle in a polygon
• Enclosing \(k\) points in the smallest axis parallel rectangle
• Finding the largest area rectangle of arbitrary orientation in a closed contour
• Placing two axis-parallel squares to maximize the number of enclosed points
• Finding largest rectangles in convex polygons
• Maximum-area and maximum-perimeter rectangles in polygons
• scientific article; zbMATH DE number 219276
• Finding squares and rectangles in sets of points

Cites Work

• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Algorithmic discrepancy beyond partial coloring
• Covering many points with a small-area box
• Enclosing \(k\) points in the smallest axis parallel rectangle
• Finding k points with minimum diameter and related problems
• Finding kth paths and p-centers by generating and searching good data structures
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Generalized Selection and Ranking: Sorted Matrices
• Geometric approximation algorithms
• Introduction to algorithms.
• Iterated nearest neighbors and finding minimal polytopes
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Static and Dynamic Algorithms for k-Point Clustering Problems
• The complexity of selection and ranking in X+Y and matrices with sorted columns

Cited In (7)

• Smallest k-enclosing rectangle revisited
• Title not available (Why is no real title available?)
• Covering many points with a small-area box
• Enclosing \(k\) points in the smallest axis parallel rectangle
• Smallest \(k\)-enclosing rectangle revisited
• Placing two axis-parallel squares to maximize the number of enclosed points
• Counting Maximal Points in a Query Orthogonal Rectangle

This page was built for publication:

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