Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points

DOI10.1016/j.comgeo.2019.01.007zbMath1427.51005OpenAlexW2919817309WikidataQ128301487 ScholiaQ128301487MaRDI QIDQ2331206

Sasanka Roy, Micha Sharir, Haim Kaplan

Publication date: 25 October 2019

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7860/

zbMATH Keywords

areadiagonalperimeteraxis-parallel rectangleenclose points

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)

Related Items (2)

Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points

Cites Work

• Unnamed Item
• Unnamed Item
• Enclosing \(k\) points in the smallest axis parallel rectangle
• Selection in \(X+Y\) and matrices with sorted rows and columns
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Geometric applications of a randomized optimization technique
• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• Finding k points with minimum diameter and related problems
• Generalized Selection and Ranking: Sorted Matrices
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Finding kth paths and p-centers by generating and searching good data structures
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Covering many points with a small-area box

This page was built for publication: Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points