Voronoi diagram with visual restriction

ISCAS OpenIR

	Voronoi diagram with visual restriction
	Fan, Chenglin (1); Luo, Jun (1); Wang, Wencheng (3); Zhu, Binhai (4); Luo, J.(jun.luo@siat.ac.cn)
	2013
发表期刊	Theoretical Computer Science
ISSN	3043975
卷号	532 页码:31-39
摘要	In a normal Voronoi diagram, each site is able to see all the points in the plane. In this paper, we study the case such that each site is only able to see a visually restricted region in the plane and construct the so-called Visual Restriction Voronoi Diagram (VRVD). We show that the visual restriction Voronoi cell of each site is not necessarily convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on n sites is Θ (n²), and then show that the VRVD can be constructed in O (n²) time and O (n²) space. Besides that, we also give another algorithm with an extra log n factor of running time to compute VRVD, which is easy to implement in practice. © 2013 Elsevier B.V. All rights reserved.; In a normal Voronoi diagram, each site is able to see all the points in the plane. In this paper, we study the case such that each site is only able to see a visually restricted region in the plane and construct the so-called Visual Restriction Voronoi Diagram (VRVD). We show that the visual restriction Voronoi cell of each site is not necessarily convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on n sites is Θ (n²), and then show that the VRVD can be constructed in O (n²) time and O (n²) space. Besides that, we also give another algorithm with an extra log n factor of running time to compute VRVD, which is easy to implement in practice. © 2013 Elsevier B.V. All rights reserved.
收录类别	SCI ; EI
关键词	Voronoi Diagram Visual Restriction Computational Geometry
部门归属	(1) Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China; (2) Huawei Noah's Ark Laboratory, Hong Kong; (3) Institute of Software, Chinese Academy of Sciences, China; (4) Department of Computer Science, Montana State University, Bozeman, MT 59717, USA
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16863
专题	中国科学院软件研究所
通讯作者	Luo, J.(jun.luo@siat.ac.cn)
推荐引用方式 GB/T 7714	Fan, Chenglin ,Luo, Jun ,Wang, Wencheng ,et al. Voronoi diagram with visual restriction[J]. Theoretical Computer Science,2013,532:31-39.
APA	Fan, Chenglin ,Luo, Jun ,Wang, Wencheng ,Zhu, Binhai ,&Luo, J..(2013).Voronoi diagram with visual restriction.Theoretical Computer Science,532,31-39.
MLA	Fan, Chenglin ,et al."Voronoi diagram with visual restriction".Theoretical Computer Science 532(2013):31-39.