Online unit covering in Euclidean space
From MaRDI portal
Publication:5919348
DOI10.1016/j.tcs.2019.12.010zbMath1436.68380arXiv1710.00954OpenAlexW2999064497WikidataQ126386081 ScholiaQ126386081MaRDI QIDQ5919348
Csaba D. Tóth, Adrian Dumitrescu, Anirban Ghosh
Publication date: 29 January 2020
Published in: Theoretical Computer Science, Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.00954
competitive ratiolower boundonline algorithmNewton numberillumination numberunit clusteringunit covering
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)
Related Items (5)
Online unit clustering and unit covering in higher dimensions ⋮ Covering a set of points with a minimum number of equal disks via simulated annealing ⋮ Hitting geometric objects online via points in \(\mathbb{Z}^d\) ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Experiments with unit disk cover algorithms for covering massive pointsets
Cites Work
- Unnamed Item
- Unnamed Item
- Better bounds on online unit clustering
- Illuminating and covering convex bodies
- An improved lower bound for one-dimensional online unit clustering
- Improved results on geometric hitting set problems
- Polynomial time approximation schemes for minimum disk cover problems
- Approximation algorithms for the unit disk cover problem in 2D and 3D
- A randomized algorithm for online unit clustering
- An improved algorithm for online unit clustering
- Clustering to minimize the maximum intercluster distance
- Optimal packing and covering in the plane are NP-complete
- Combinatorial problems on the illumination of convex bodies
- On kissing numbers in dimensions 32 to 128
- Online unit clustering in higher dimensions
- On kissing numbers and spherical codes in high dimensions
- The geometry of homothetic covering and illumination
- The Design of Approximation Algorithms
- Research Problems in Discrete Geometry
- Online Primal-Dual Algorithms for Covering and Packing
- On the online unit clustering problem
- On the Complexity of Some Common Geometric Location Problems
- The Online Set Cover Problem
- Approximation schemes for covering and packing problems in image processing and VLSI
- Incremental Clustering and Dynamic Information Retrieval
- Drei Sätze über die n-dimensionale euklidische Sphäre
- A survey on the kissing numbers
- The Closest Packing of Spherical Caps in n Dimensions
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
This page was built for publication: Online unit covering in Euclidean space
