PLANAR POINT LOCATION REVISITED

作     者：FRANCO P. PREPARATA 

作者机构：Coordinated Science Laboratory University of Illinois Urbana IL 61801 USA This work was supported in part by the Joint Services Electronics Program under Contract N00014–84-C-0149. 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1990年第1卷第1期

页      面：71-86页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：computational geometry planar point location dynamic data structures persistence fractional cascading 

摘      要：Point location is a fundamental primitive in Computational Geometry. In the plane it is stated as follows: Given a subdivision ℛ of the plane and a query point q , determine the region of ℛ containing q . We survey the work that has led to practical algorithms for the static version of the problem, and discuss current research on the corresponding dynamic algorithms.