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

DOI10.1016/J.COMGEO.2019.01.007zbMATH Open1427.51005OpenAlexW2919817309WikidataQ128301487 ScholiaQ128301487MaRDI QIDQ2331206FDOQ2331206

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/

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

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)

Cites Work

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

Cited In (7)

• Cause I'm a genial imprecise point: outlier detection for uncertain data
• Title not available (Why is that?)
• 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)