凸包

几何求交

三角剖分

Voronoi图

Delaunay三角剖分

点定位

范围查询 (点定位的对偶)

  • kd-Tree

截窗查询 (范围查询的扩展：点-线-面-体)

注：所有图像转自邓俊晖老师的《计算几何》课程。