Abstract
Transportation networks model facilities for fast movement on the plane. A transportation network, together with its underlying distance, induces a new distance. Previously, only the Euclidean and the L 1 distances have been considered as such underlying distances. However, this paper first considers distances induced by general distances and transportation networks, and present a unifying approach to compute Voronoi diagrams under such a general setting. With this approach, we show that an algorithm for convex distances can be easily obtained.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Proximity problems for time metrics induced by the l 1 metric and isothetic networks. In: IX Encuetros en Geometria Computacional (2001)
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Voronoi diagram for services neighboring a highway. Information Processing Letters 86, 283–288 (2003)
Aichholzer, O., Aurenhammer, F., Palop, B.: Quickest paths, straight skeletons, and the city voronoi diagram. In: Proceedings of the 8th SoCG, pp. 151–159 (2002)
Bae, S.W., Chwa, K.-Y.: Voronoi diagrams with a transportation network on the euclidean plane. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 101–112. Springer, Heidelberg (2004), Technical report, Korea Advanced Institute of Science and Technology (2005)
Corbalan, A.G., Mazon, M., Recio, T.: Geometry of bisectors for strictly convex distances. International Journal of Computertational Gemoetry and Applications 6(1), 45–58 (1996)
Dehne, F., Klein, R.: The big sweep: On the power of the wavefront approach to Voronoi diagrams. Algorithmica 17, 19–32 (1997)
Gewali, L., Meng, A., Mitchell, J.S.B., Ntafos, S.: Path planning in 0/1/ ∞ weighted regions with applications. ORSA J. Comput. 2(3), 253–272 (1990)
Görke, R., Wolff, A.: Computing the city voronoi diagram faster. In: Proc. 21st Euro. Workshop on Comput. Geom., pp. 155–158 (2005)
Kelly, J.C.: Bitopological spaces. Proc. London Math. Soc. 13(3), 71–89 (1963)
Klein, R.: Concrete and Abstract Voronoi Diagrams. LNCS, vol. 400. Springer, Heidelberg (1989)
Klein, R.: Private communication (2005)
Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract voronoi diagrams. Computational Geometry: Theory and Applications 3, 157–184 (1993)
Klein, R., Wood, D.: Voronoi diagrams based on general metrics in the plane. In: Cori, R., Wirsing, M. (eds.) STACS 1988. LNCS, vol. 294, pp. 281–291. Springer, Heidelberg (1988)
Ma, L.: Bisectors and Voronoi Diagams for Convex Distance Functions. PhD thesis, Fern Unversität Hagen (2000)
Mehlhorn, K., Meiser, S., O’Dunlaing, C.: On the construction of abstract Voronoi diagrams. Discrete Comput. Geom. 6, 211–224 (1991)
Mennucci, A.C.G.: On asymmetric distances. Preprint (2004), available at http://cvgmt.sns.it/cgi/get.cgi/papers/and04/
Mitchell, J.S.B.: Shortest paths among obstacles, zero-cost regions, and “roads”. Technical Report 764, School Oper. Res. Indust. Engrg., Cornell Univ., Ithaca, NY (1987)
Palop, B.: Algorithmic problems on proximity and location under metric constraints. PhD thesis, U. Politécnica de Catalunya (2003)
Rinow, W.: Die innere Geometrie der Metrischen Räume. Grundlehren der Mathematischen Wissenschaften in Einzeldarstellungen, vol. 105. Springer, Berlin (1961)
Rowe, N.C.: Roads, rivers, and obstacles: optimal two-dimensional path planning around linear features for a mobile agent. Internat. J. Robot. Res. 9, 67–73 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bae, S.W., Chwa, KY. (2005). Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_100
Download citation
DOI: https://doi.org/10.1007/11602613_100
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)