Translating a regular grid over a point set

DOI10.1016/S0925-7721(02)00128-1MaRDI QIDQ1873153zbMATH OpenOpenAlexWikidataFDO

Authors Prosenjit Bose, Anil Maheshwari, Pat Morin, Jason Morrison, Marc Van Kreveld

Publication date 19 May 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(02)00128-1

zbMATH Keywords

binary treedynamic data structurefacility locationintervalslazy updatemaintenance of functions

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

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.

Recommendations

• Approximation of a set of points by points of a grid
• Algorithms and Computation
• scientific article; zbMATH DE number 3058521
• REGULAR ENUMERATION OF GRID POINTS IN A CONVEX POLYGON
• Point configurations and translations
• The m-dimensional grid point space
• scientific article; zbMATH DE number 3905323
• scientific article; zbMATH DE number 1947380
• On grids in point-line arrangements in the plane
• On Grids in Point-Line Arrangements in the Plane

Cites work

• Algorithms for projecting points to give the most uniform distribution with applications to hashing
• Algorithms for Reporting and Counting Geometric Intersections
• Concatenable segment trees (extended abstract)
• Finding the upper envelope of n line segments in O(n log n) time
• Geometric Problems with Application to Hashing
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1522945 (Why is no real title available?)
• Making data structures persistent

Cited in

(5)

• On simplifying dot maps.
• Improved Grid Map Layout by Point Set Matching
• The m-dimensional grid point space
• scientific article; zbMATH DE number 1830732 (Why is no real title available?)
• Covering many or few points with unit disks

This page was built for publication: Translating a regular grid over a point set

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