首页> 外文OA文献 >A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains
【2h】

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

机译:一种简单多边形和其他受限多边形域中点的测地线Voronoi图的新方法

摘要

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L 1 metric.
机译:我们介绍了一种用于计算简单多边形和其他受限多边形域中点站点的测地Voronoi图的新方法。我们的方法将多边形域的扫描与常规分而治之算法的合并步骤结合在一起。时间复杂度为O((n + k)log(n + k)),其中n是顶点数,k是点数,在以前已知的范围内有所改进。空间是O(n + k)。适用于我们方法的其他多边形区域包括(其中包括)平行不相交线段的多边形区域和L 1度量中的矩形的多边形区域。

著录项

  • 作者

    E.Papadopoulou; D.T.Lee;

  • 作者单位
  • 年度 2014
  • 总页数
  • 原文格式 PDF
  • 正文语种 en_us
  • 中图分类

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号