Labeling Smart Dust

V. Bansal, F. Meyer auf der Heide, C. Sohler, in: 12th Annual European Symposium on Algorithms (ESA 2004), Berlin, Heidelberg, 2004.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
; ;
Abstract
Given n distinct points p1, p2, ... , pn in the plane, the map labeling problem with four squares is to place n axis-parallel equi-sized squares Q1, ... ,Qn of maximum possible size such that pi is a corner of Qi and no two squares overlap. This problem is NP-hard and no algorithm with approximation ratio better than 1/2 exists unless P = NP [10]. In this paper, we consider a scenario where we want to visualize the information gathered by smart dust, i.e. by a large set of simple devices, each consisting of a sensor and a sender that can gather sensor data and send it to a central station. Our task is to label (the positions of) these sensors in a way described by the labeling problem above. Since these devices are not positioned accurately (for example, they might be dropped from an airplane), this gives rise to consider the map labeling problem under the assumption, that the positions of the points are not fixed precisely, but perturbed by random noise. In other words, we consider the smoothed complexity of the map labeling problem. We present an algorithm that, under such an assumption and Gaussian random noise with sufficiently large variance, has linear smoothed complexity.
Publishing Year
Proceedings Title
12th Annual European Symposium on Algorithms (ESA 2004)
Volume
3221
LibreCat-ID

Cite this

Bansal V, Meyer auf der Heide F, Sohler C. Labeling Smart Dust. In: 12th Annual European Symposium on Algorithms (ESA 2004). Vol 3221. Lecture Notes in Computer Science. Berlin, Heidelberg; 2004. doi:10.1007/978-3-540-30140-0_9
Bansal, V., Meyer auf der Heide, F., & Sohler, C. (2004). Labeling Smart Dust. In 12th Annual European Symposium on Algorithms (ESA 2004) (Vol. 3221). Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_9
@inproceedings{Bansal_Meyer auf der Heide_Sohler_2004, place={Berlin, Heidelberg}, series={Lecture Notes in Computer Science}, title={Labeling Smart Dust}, volume={3221}, DOI={10.1007/978-3-540-30140-0_9}, booktitle={12th Annual European Symposium on Algorithms (ESA 2004)}, author={Bansal, Vikas and Meyer auf der Heide, Friedhelm and Sohler, Christian}, year={2004}, collection={Lecture Notes in Computer Science} }
Bansal, Vikas, Friedhelm Meyer auf der Heide, and Christian Sohler. “Labeling Smart Dust.” In 12th Annual European Symposium on Algorithms (ESA 2004), Vol. 3221. Lecture Notes in Computer Science. Berlin, Heidelberg, 2004. https://doi.org/10.1007/978-3-540-30140-0_9.
V. Bansal, F. Meyer auf der Heide, and C. Sohler, “Labeling Smart Dust,” in 12th Annual European Symposium on Algorithms (ESA 2004), 2004, vol. 3221.
Bansal, Vikas, et al. “Labeling Smart Dust.” 12th Annual European Symposium on Algorithms (ESA 2004), vol. 3221, 2004, doi:10.1007/978-3-540-30140-0_9.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search