請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38480
標題: Two Dimensional Voronoi Diagrams in the Lp-metric
作者: D.T.Lee
關鍵字: Voronoi diagram, L,-metric, computational geometry, computational complexity, analysis of algorithm, divide-and-conquer
出版社: ACM New York, NY, USA
摘要: The Voronoi diagram, also known as the Thiessen diagram, for a set of N points in the Cartesian plane in which the L,-metnc is the distance measure, where p is a real number between 1 and 0o inclusive, is defined, and an algorithm for constructing the dmgram m O(NlogN) tune is presented This algonthm uses the divide-and-conquer technique. Many proximity problems revolving a set of points, such as finding the nearest neighbor of a given point, finding the minimum spamung tree, findmg the smallest circle (m the Lp-metric) enclosing the point set, etc., can be solved very efficiently via the diagram The running time of the algorithm presented is also shown to be optimal to within a constant factor
URI: http://hdl.handle.net/11455/38480
ISSN: 0004-5411
顯示於類別:資訊科學與工程學系所

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


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