Two-site Voronoi diagrams in geographic networks

ABSTRACT

We provide an efficient algorithm for two-site Voronoi diagrams in geographic networks. A two-site Voronoi diagram labels each vertex in a geographic network with their two nearest neighbors, which is useful in many contexts.

REFERENCES

• 1: M. Abellanas , F. Hurtado , V. Sacristán , C. Icking , L. Ma , R. Klein , E. Langetepe , B. Palop, Voronoi Diagram for services neighboring a highway, Information Processing Letters, v.86 n.5, p.283-288, 15 June 2003 [doi>10.1016/S0020-0190(02)00505-7]
• 2: Oswin Aichholzer , Franz Aurenhammer , Belén Palop, Quickest paths, straight skeletons, and the city Voronoi diagram, Proceedings of the eighteenth annual symposium on Computational geometry, p.151-159, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513420]
• 3: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 4: F. Aurenhammer and R. Klein. Voronoi diagrams. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 201--290. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
• 5: S. W. Bae and K.-Y. Chwa. Voronoi diagrams with a transportation network on the euclidean plane. In Proc. Int. Symp. on Algorithms and Computation (ISAAC), volume 3341 of LNCS, pages 101--112. Springer, 2004.
• 6: S. W. Bae and K.-Y. Chwa. Shortest paths and Voronoi diagrams with transportation networks under general distances. In Proc. Int. Symp. on Algorithms and Computation (ISAAC), volume 3827 of LNCS, pages 1007--1018. Springer, 2005.
• 7: Gill Barequet , Matthew T. Dickerson , Robert L. Scot Drysdale, 2-Point site Voronoi diagrams, Discrete Applied Mathematics, v.122 n.1-3, p.37-54, 15 October 2002 [doi>10.1016/S0166-218X(01)00320-1]
• 8: Gill Barequet , Robert L. Scot , Matthew T. Dickerson , David S. Guertin, 2-point site Voronoi diagrams, Proceedings of the seventeenth annual symposium on Computational geometry, p.323-324, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378723]
• 9: B. Chazelle , H. Edelsbrunner, An improved algorithm for constructing kth-order voronoi diagrams, IEEE Transactions on Computers, v.36 n.11, p.1349-1354, Nov. 1987 [doi>10.1109/TC.1987.5009474]
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: Victor Teixeira de Almeida , Ralf Hartmut Güting, Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141291]
• 12: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 13: G. L. Dirichlet. Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. J. Reine Angew. Math., 40:209--227, 1850.
• 14: M. Erwig. The graph Voronoi diagram with applications. Networks, 36(3):156--163, 2000.
• 15: S. Fortune. Voronoi diagrams and Delaunay triangulations. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 1 of Lecture Notes Series on Computing, pages 193--233. World Scientific, Singapore, 1st edition, 1992.
• 16: M. T. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, New York, NY, 2002.
• 17: Ferran Hurtado , Rolf Klein , Elmar Langetepe , Vera Sacristán, The weighted farthest color Voronoi diagram on trees and graphs, Computational Geometry: Theory and Applications, v.27 n.1, p.13-26, January 2004 [doi>10.1016/j.comgeo.2003.07.003]
• 18: D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973.
• 19: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 20: Der-Tsai Lee, On k-Nearest Neighbor Voronoi Diagrams in the Plane, IEEE Transactions on Computers, v.31 n.6, p.478-487, June 1982 [doi>10.1109/TC.1982.1676031]
• 21: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 22: Kostas Patroumpas , Theofanis Minogiannis , Timos Sellis, Approximate order-k Voronoi cells over positional streams, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341059]
• 23: Maytham Safar, K nearest neighbor search in navigation systems, Mobile Information Systems, v.1 n.3, p.207-224, August 2005
• 24: K. Sugihara. Algorithms for computing Voronoi diagrams. In A. Okabe, B. Boots, and K. Sugihara, editors, Spatial Tesselations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 1992.
• 25: G. M. Voronoi. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. premier Mémoire: Sur quelques propriétés des formes quadratiques positives parfaites. J. Reine Angew. Math., 133:97--178, 1907.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Keywords:
Voronoi diagrams, geographic graphs, shortest paths