請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38506
標題: Location of a Point in a Planar Subdivision and Its Applications
作者: D.T.Lee
F.P.Preparata
出版社: ACM New York, NY, USA �1976
摘要: Given a subdivision of the plane induced by a planar graph with n vertices, in this paper we consider the problem of identifying which region of the subdivision contains a given test point. We present a search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure. The search runs in time at most 0((log n)2), while the preprocessing task runs in time at most 0(n log n) and requires 0(n) storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most 0(n log n) into one to which the preprocessing procedure is applicable. This solution of the point-location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon.
URI: http://hdl.handle.net/11455/38506
顯示於類別:資訊科學與工程學系所

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


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