Translating a regular grid over a point set
type: Item
instance of: scholarly article
title: Translating a regular grid over a point set
zbMATH Open document ID: 1021.65008
DOI: 10.1016/S0925-7721(02)00128-1
author: Prosenjit Bose
author: Anil Maheshwari
author: Pat Morin
author: Jason Morrison
author: Marc Van Kreveld
published in: Computational Geometry
publication date: 2003-05-19T00:00:00Z
review text: The authors consider the problem of translating a finite or infinity square grid \(G\) over a set \(S\) of \(n\) points in the plane in order to maximize some objective function. A grid cell in \(k\)-occupied if it contains \(K\) or more points of \(S\). The main set of problems studied have to do with translating an infinity grid so that the number of \(k\)-occupied cells is maximized or minimized. For these problems running times of the form \(O(kn\text{ poly log}(n))\) are obtained. Also the problem of translating a finite size grid, with \(m\) cells, is considered in order to maximize the number of \(k\)-occupied cells.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 1912421
zbMATH Keywords: dynamic data structure
zbMATH Keywords: binary tree
zbMATH Keywords: intervals
zbMATH Keywords: lazy update
zbMATH Keywords: facility location
zbMATH Keywords: maintenance of functions
Wikidata QID: Q57009436
reviewed by: Francisco Pérez Acosta
MaRDI profile type: Publication
cites work: Q4511241
cites work: Algorithms for projecting points to give the most uniform distribution with applications to hashing
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: Geometric Problems with Application to Hashing
cites work: Q3619797
cites work: Q4344150
cites work: Making data structures persistent
cites work: Finding the upper envelope of n line segments in O(n log n) time
cites work: Concatenable segment trees
full work available at URL: s0925-7721(02)00128-1
OpenAlex ID: W2127927089
Recommended article: Approximation of a set of points by points of a grid
Recommended article: Algorithms and Computation
Recommended article: Q5797649
Recommended article: REGULAR ENUMERATION OF GRID POINTS IN A CONVEX POLYGON
Recommended article: Point configurations and translations
Recommended article: The m-dimensional grid point space
Recommended article: Q3683086
Recommended article: Q4411344
Recommended article: On grids in point-line arrangements in the plane
Recommended article: On Grids in Point-Line Arrangements in the Plane
description: scientific article; zbMATH DE number 1912421