›› 2013, Vol. 28 ›› Issue (2): 267-277.doi: 10.1007/s11390-013-1328-2

Special Issue: Computer Graphics and Multimedia

• Theoretical Computer Science • Previous Articles     Next Articles

On 2-Site Voronoi Diagrams Under Geometric Distance Functions

Gill Barequet1, Matthew Dickerson2, David Eppstein3, Fellow, ACM, David Hodorkovsky4 and Kira Vyatkina5, Member, ACM   

  1. 1 Department of Computer Science, Technion-Israel Institute of Technology, Haifa 32000, Israel;
    2 Department of Mathematics and Computer Science, Middlebury College, Middlebury 05753, U.S.A.;
    3 Department of Mathematics and Computer Science, University of California, Irvine 92717, U.S.A.;
    4 Department of Applied Mathematics, Technion-Israel Institute of Technology, Haifa 32000, Israel;
    5 Algorithmic Biology Laboratory, St. Petersburg Academic University, Russian Academy of Sciences, 8/3 Khlopina St.St Petersburg 194021, Russia
  • Received:2012-02-10 Revised:2012-09-03 Online:2013-03-05 Published:2013-03-05
  • Supported by:

    David Eppstein was supported by National Science Foundation of USA under Grants Nos. 0830403 and 1217322 and US Office of Naval Research under Grant No. N00014-08-1-1015.

We revisit a new type of Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, namely, circles and triangles, and analyze the structure and complexity of the nearest- and furthest-neighbor 2-site Voronoi diagrams of a point set in the plane with respect to these distance functions. In addition, we bring to notice that 2-point site Voronoi diagrams can be alternatively interpreted as 1-site Voronoi diagrams of segments, and thus, our results also enhance the knowledge on the latter.

[1] Aurenhammer F. Voronoi diagram - A survey of a fundamen-tal geometric data structure. ACM Computing Surveys, 1991,23(3): 345-405.

[2] Okabe A, Boots A, Sugihara B, Chui S N. Spatial Tessela-tions: Concepts and Applications of Voronoi Diagrams (2ndedition). John Wiley and Sons, Inc., 2000.

[3] GavrilovaML E. Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence. SpringerPublishing Company, 2008.

[4] Barequet G, Dickerson M, Drysdale III R L S. 2-point siteVoronoi diagrams. In Proc. the 6th International Workshopon Algorithms and Data Structures, Aug. 1999, pp.219-230.

[5] Roth K F. On a problem of Heilbronn. Proc. London Math-ematical Society, 1951, 26: 198-204.

[6] Vyatkina K, Barequet G. On 2-site Voronoi diagrams underarithmetic combinations of point-to-point distances. In Proc.the 7th Int. Symp. Voronoi Diagrams in Science and Engi-neering, June 2010, pp.33-41.

[7] Dickerson M T, Eppstein D. Animating a continuous familyof two-site Voronoi diagrams (and a proof of a bound on thenumber of regions). In Proc. the 25th Annual Symposium onComputational Geometry, June 2009, pp.92-93.

[8] Hanniel I, Barequet G. On the triangle-perimeter two-siteVoronoi diagram. In Proc. the 6th Int. Symp. VoronoiDiagrams, June 2009, pp.129-136.

[9] Hodorkovsky D. 2-point site Voronoi diagrams [M.Sc. Thesis].Technion-Israel Inst. of Technology, Haifa, Israel, 2005.

[10] Asano T, Tamaki H, Katoh N, Tokuyama T. Angular Voronoidiagram with applications. In Proc. the 3rd Int. Symp.Voronoi Diagrams in Science and Engineering, July 2006,pp.18-24.

[11] Asano T, Katoh N, Tamaki H, Tokuyama T. Voronoi dia-grams with respect to criteria on vision information. In Proc.the 4th Int. Symp. Voronoi Diagrams in Science and Engi-neering, July 2007, pp.25-32.

[12] Sharir M, Agarwal P K. Davenport-Schinzel Sequences andTheir Geometric Application. Cambridge University Press,1995.

[13] de Berg M, Cheong O, van Kreveld M, Overmars M. Com-putational Geometry, Algorithms, and Applications (3rd edi-tion). Springer-Verlag, Berlin TELOS, 2008.

[14] Ajtai M, Chvátal V, Newborn M, Szemerédi E. Crossing-freesubgraphs. Theory and Practice of Combinatorics; North-Holland Mathematics Studies, 1982, 60: 9-12.

[15] Leighton F. Complexity Issues in VLSI. Cambridge, MA: MITPress, 1983.
No related articles found!
Full text



[1] Zhou Chaochen; Liu Xinxin;. Denote CSP with Temporal Formulas[J]. , 1990, 5(1): 17 -23 .
[2] Jiang Changjun; Wu Zhehui;. Net Operations[J]. , 1992, 7(4): 333 -344 .
[3] Li Deyi;. Knowledge Representation in KDD Based on Linguistic Atoms[J]. , 1997, 12(6): 481 -496 .
[4] Wu Hong; Nie Xumin;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[5] Sheng-Zhi Du, Zeng-Qiang Chen, and Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory[J]. , 2005, 20(4): 559 -566 .
[6] Hai-Bo Tian, Xi Sun, and Yu-Min Wang. A New Public-Key Encryption Scheme[J]. , 2007, 22(1): 95 -02 .
[7] Yong Xi, Ke-Wei Sha, Wei-Song Shi, Loren Schwiebert, and Tao Zhang. Probabilistic Adaptive Anonymous Authentication in Vehicular Networks[J]. , 2008, 23(6 ): 916 -928 .
[8] Gang Wu, Juan-Zi Li, Member, CCF, ACM, Jian-Qiang Hu, and Ke-Hong Wang, Member, CCF. System |Π: A Native RDF Repository Based on the Hypergraph Representation for RDF Data Model[J]. , 2009, 24(4): 652 -664 .
[9] Chun-Tao Hong (洪春涛), Member, CCF, De-Hao Chen (陈德颢), Member, CCF, Yu-Bei Chen (陈羽北), Wen-Guang Chen (陈文光), Member, CCF, ACM, IEEE, Wei-Min Zheng (郑纬民), Member, CCF, ACM, IEEE and Hai-Bo Lin (林海波), Member, ACM, IEEE. Providing Source Code Level Portability Between CPU and GPU with MapCG[J]. , 2012, 27(1): 42 -56 .
[10] Rong Yang (杨荣), Zhao-Lan Yang (杨兆兰), and He-Ping Zhang (张和平). Some Indices of Alphabet Overlap Graph[J]. , 2012, 27(4): 897 -902 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved