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

DOI10.1016/J.COMGEO.2019.01.007MaRDI QIDQ2331206zbMATH OpenOpenAlexWikidataFDO

Authors Sasanka Roy, Haim Kaplan, Micha Sharir

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

areaperimeterdiagonalaxis-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)

Recommendations

• scientific article; zbMATH DE number 7205030
• Enclosing k points in the smallest axis parallel rectangle
• Covering many points with a small-area box
• Finding largest rectangles in convex polygons
• Efficient algorithms for the largest rectangle problem

Cites work

• scientific article; zbMATH DE number 437530 (Why is no real title available?)
• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Covering many points with a small-area box
• Enclosing k points in the smallest axis parallel rectangle
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• 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 applications of a randomized optimization technique
• Geometric approximation algorithms
• 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)

• Cause I'm a genial imprecise point: outlier detection for uncertain data
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Enclosing k points in the smallest axis parallel rectangle
• A novel approximation algorithm for max-covering circle problem
• Placing two axis-parallel squares to maximize the number of enclosed points
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• Counting Maximal Points in a Query Orthogonal Rectangle

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

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