We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 28 Issue 2
March  2013
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Gill Barequet, Matthew Dickerson, David Eppstein, David Hodorkovsky, Kira Vyatkina. On 2-Site Voronoi Diagrams Under Geometric Distance Functions[J]. Journal of Computer Science and Technology, 2013, 28(2): 267-277. DOI: 10.1007/s11390-013-1328-2
Citation: Gill Barequet, Matthew Dickerson, David Eppstein, David Hodorkovsky, Kira Vyatkina. On 2-Site Voronoi Diagrams Under Geometric Distance Functions[J]. Journal of Computer Science and Technology, 2013, 28(2): 267-277. DOI: 10.1007/s11390-013-1328-2
shu

On 2-Site Voronoi Diagrams Under Geometric Distance Functions

  • 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

Funds: 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.
More Information
  • Received Date: February 09, 2012
  • Revised Date: September 02, 2012
  • Published Date: March 04, 2013
    Abstract
  • 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.
    • FullText(HTML)
    • References (15)
  • [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.
    • Relative Articles

  • Related Articles

    [1]Feng Jiang, Huai-Min Wang, Pei-Chang Shi, Xiang Fu, Liao-Liao Feng, Rui Li, Mo-Heng Lin. An Understandable Cross-Chain Authentication Mechanism for JointCloud Computing[J]. Journal of Computer Science and Technology. DOI: 10.1007/s11390-025-4733-4
    [2]Ying Li, Jia-Jie Xu, Peng-Peng Zhao, Jun-Hua Fang, Wei Chen, Lei Zhao. ATLRec: An Attentional Adversarial Transfer Learning Network for Cross-Domain Recommendation[J]. Journal of Computer Science and Technology, 2020, 35(4): 794-808. DOI: 10.1007/s11390-020-0314-8
    [3]Zhou Xu, Shuai Pang, Tao Zhang, Xia-Pu Luo, Jin Liu, Yu-Tian Tang, Xiao Yu, Lei Xue. Cross Project Defect Prediction via Balanced Distribution Adaptation Based Transfer Learning[J]. Journal of Computer Science and Technology, 2019, 34(5): 1039-1062. DOI: 10.1007/s11390-019-1959-z
    [4]Chao Ni, Wang-Shu Liu, Xiang Chen, Qing Gu, Dao-Xu Chen, Qi-Guo Huang. A Cluster Based Feature Selection Method for Cross-Project Software Defect Prediction[J]. Journal of Computer Science and Technology, 2017, 32(6): 1090-1107. DOI: 10.1007/s11390-017-1785-0
    [5]Meng Chen, Lin-Lin Zhang, Xiaohui Yu, Yang Liu. Weighted Co-Training for Cross-Domain Image Sentiment Classification[J]. Journal of Computer Science and Technology, 2017, 32(4): 714-725. DOI: 10.1007/s11390-017-1753-8
    [6]Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu. Optimal Path Embedding in the Exchanged Crossed Cube[J]. Journal of Computer Science and Technology, 2017, 32(3): 618-629. DOI: 10.1007/s11390-017-1729-8
    [7]Li-Feng He, Yu-Yan Chao, Kenji Suzuki. An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing[J]. Journal of Computer Science and Technology, 2013, 28(3): 468-478. DOI: 10.1007/s11390-013-1348-y
    [8]Bo Lu, Guo-Ren Wang, Ye Yuan. A Novel Approach Towards Large Scale Cross-Media Retrieval[J]. Journal of Computer Science and Technology, 2012, 27(6): 1140-1149. DOI: 10.1007/s11390-012-1292-2
    [9]Qing-Hua Zheng, David L. Pepyne, Qing Wang. New Approach to WLAN Security with Synchronized Pseudo Random[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [10]Luo Yinfang. Algorithm and Implementation of Parallel Multiplication in a Mixed Number System[J]. Journal of Computer Science and Technology, 1988, 3(3): 203-213.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (25) PDF downloads (1362) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return