請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38274
標題: Skew Voronoi Diagram
作者: O.Aichholzer
F.Aurenhammer
D.Z.Chen
D.T.Lee
E.Papadopoulou
關鍵字: Direction-dependent distance
Voronoi diagram
additive weights
output-sensitive algorithm
摘要: On a tilted plane T in three-space, skew distances are defined as the Euclidean distance plus a multiple of the signed difference in height. Skew distances may model realistic environments more closely than the Euclidean distance. Voronoi diagrams and related problems under this kind of distances are investigated. A relationship to convex distance functions and to Euclidean Voronoi diagrams for planar circles is shown, and is exploited for a geometric analysisis and a plane-sweep construction of Voronoi diagrams on T. An output-sensitive algorithm running in time O(n log h) is developed, where n and h are the numbers of sites and non-empty Voronoi regions, respectively. The all nearest neighbors problem for skew distances, which has certain features different from its Euclidean counterpart, is solved in O(n log n) time
URI: http://hdl.handle.net/11455/38274
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。