A simple factor-3 approximation for labeling points with circles. (English) Zbl 1161.68878
Summary: We present a simple factor-\((3+\varepsilon)\), \(0<\varepsilon <1\), approximation algorithm, which runs in \(O(n\log n+n(1/\varepsilon)^{O(1/\varepsilon^{2})}\log (D_{3}/\varepsilon D_{2}))\) time, for the problem of labeling a set \(P\) of \(n\) distinct points with uniform circles. (\(D_{2}\) is the closest pair of \(P\) and \(D_{3}\) is the minimum diameter of all subsets of \(P\) with size three.) This problem is known to be NP-hard. Our bound improves the previous factor of \(3.6+\varepsilon\).
MSC:
| 68W25 | Approximation algorithms |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Datta, A.; Lenhof, H.-P.; Schwarz, C.; Smid, M., Static and dynamic algorithms for \(k\)-point clustering problems, J. Algorithms, 19, 474-503 (1995) · Zbl 0836.68115 |
| [2] | Doddi, S.; Marathe, M.; Moret, B., Point set labeling with specified positions, Internat. J. Comput. Geom. Appl., 12, 1-2, 29-66 (2002) · Zbl 1053.65013 |
| [3] | Doddi, S.; Marathe, M.; Mirzaian, A.; Moret, B.; Zhu, B., Map labeling and its generalizations, (Proc. 8th ACM-SIAM Symp. on Discrete Algorithms (SODA’97), New Orleans, LA (1997)), 148-157 · Zbl 1321.68435 |
| [4] | Eppstein, D.; Erickson, J., Iterated nearest neighbors and finding minimal polytopes, Discrete Comput. Geom., 11, 321-350 (1994) · Zbl 0807.68094 |
| [5] | Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer: Springer Berlin · Zbl 0759.68037 |
| [6] | Strijk, T.; Wolff, A., Labeling points with circles, Internat. J. Comput. Geom. Appl., 11, 2, 181-195 (2001) · Zbl 1074.68653 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
