voronoi diagram with visual restriction

CORC > 软件研究所 > 软件所图书馆 > 会议论文

	voronoi diagram with visual restriction
	Fan Chenglin ; Luo Jun ; Wang Wencheng ; Zhu Binhai
	2012
会议名称	6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
会议日期	May 14, 2012 - May 16, 2012
会议地点	Beijing, China
关键词	Algorithms Computational geometry
页码	36-46
中文摘要	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 necessary convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on n sites is Θ(n ²). Then we give an O(n ²logn) time and O(n ²) space algorithm to construct VRVD. © 2012 Springer-Verlag.
英文摘要	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 necessary convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on n sites is Θ(n ²). Then we give an O(n ²logn) time and O(n ²) space algorithm to construct VRVD. © 2012 Springer-Verlag.
收录类别	EI
会议录	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
语种	英语
ISSN号	0302-9743
ISBN号	9783642296994
内容类型	会议论文
源URL	[http://ir.iscas.ac.cn/handle/311060/15722]
专题	软件研究所_软件所图书馆_会议论文
推荐引用方式 GB/T 7714	Fan Chenglin,Luo Jun,Wang Wencheng,et al. voronoi diagram with visual restriction[C]. 见:6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012. Beijing, China. May 14, 2012 - May 16, 2012.