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

所属专题： Computer Graphics and Multimedia

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

基于几何距离函数的两点集Voronoi图

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

  • 收稿日期:2012-02-10 修回日期:2012-09-03 出版日期:2013-03-05 发布日期:2013-03-05

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.

PDF (PC)

1375

我们对一种新的Voronoi类型进行了回顾, 在这种Voronoi类型中距离的定义为从一点到一对点。我们基于几何元素, 比如圆和三角形, 考虑了一些更多的这种类型的距离函数并分析了最近和最远两点集diagrams图的结构和复杂度。此外, 我们还关注了两点集Voronoi图可以被替换的理解为线段的一点集Voronoi图。因此, 我们的结果比之前的更丰富。

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.

[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!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 周巢尘; 柳欣欣;. Denote CSP with Temporal Formulas[J]. , 1990, 5(1): 17 -23 .
[2] 蒋昌俊; 吴哲辉;. Net Operations[J]. , 1992, 7(4): 333 -344 .
[3] 李德毅;. Knowledge Representation in KDD Based on Linguistic Atoms[J]. , 1997, 12(6): 481 -496 .
[4] 吴虹; 聂旭民;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[5] . 双向联想记忆网络的进化准松弛算法(EPRBAM)[J]. , 2005, 20(4): 559 -566 .
[6] . 一种新的公钥加密方案[J]. , 2007, 22(1): 95 -02 .
[7] . 暂缺[J]. , 2008, 23(6 ): 916 -928 .
[8] 吴刚, 李涓子, 胡建强, 王克宏. System Π：一个基于RDF数据模型的超图表示的原生RDF存储系统[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. 使用MapCG进行CPU,GPU统一编程[J]. , 2012, 27(1): 42 -56 .
[10] Rong Yang (杨荣), Zhao-Lan Yang (杨兆兰), and He-Ping Zhang (张和平). 字母重叠图的一些指标[J]. , 2012, 27(4): 897 -902 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：