×

Connecting red cells in a bicolour Voronoi diagram. (English) Zbl 1374.68624

Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 210-219 (2012).
Summary: Let \(S\) be a set of \(n + m\) sites, of which \(n\) are red and have weight \(w _{R }\), and \(m\) are blue and weigh \(w_{B }\). The objective of this paper is to calculate the minimum value of the red sites’ weight such that the union of the red Voronoi cells in the weighted Voronoi diagram of \(S\) is a connected region. This problem is solved for the multiplicatively-weighted Voronoi diagram in \(\mathcal{O}((n+m)^2 \log (nm))\) time and for both the additively-weighted and power Voronoi diagram in \(\mathcal{O}(nm \log (nm))\) time.
For the entire collection see [Zbl 1253.68016].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aichholzer, O., Fabila-Monroy, R., Hackl, T., van Kreveld, M., Pilz, A., Ramos, P., Vogtenhuber, B.: Blocking delaunay triangulations. In: 22nd Canadian Conference on Computational Geometry, pp. 21–24 (2010) · Zbl 1254.05118
[2] Aurenhammer, F.: Voronoi diagrams a survey. Tech. rep., Institute for Information Processing Technical University of Graz (1988) · Zbl 0642.52008
[3] Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted voronoi diagram in the plane. Pattern Recognition 17(2), 251–257 (1984) · Zbl 0539.52008 · doi:10.1016/0031-3203(84)90064-5
[4] Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 201–290. North-Holland, Amsterdam (2000) · Zbl 0995.65024 · doi:10.1016/B978-044482537-7/50006-1
[5] Balaban, I.J.: An optimal algorithm for finding segments intersections. In: 11th Annual Symposium on Computational Geometry, SCG 1995, pp. 211–219. ACM, New York (1995)
[6] de Berg, M., Gerrits, D., Khosravi, A., Rutter, I., Tsirogiannis, C., Wolff, A.: How alexander the great brought the greeks together while inflicting minimal damage to the barbarians. In: 26th European Workshop on Computational Geometry, pp. 73–77 (2010)
[7] Golomb, S., Baumert, L.: Backtrack programming. Journal of ACM 12(4), 516–524 (1965) · Zbl 0139.12305 · doi:10.1145/321296.321300
[8] Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane – a survey. In: Discrete and Computational Geometry, The Goodman - Pollack Festschrift, pp. 551–570. Springer (2003) · Zbl 1079.52505
[9] Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations - Concepts and Applications of Voronoi Diagrams, 2nd edn. Series in Probability and Statistics. John Wiley & Sons, Inc., New York (2000) · Zbl 0946.68144 · doi:10.1002/9780470317013
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.