摘要
本文为构建离散点的凸包提出了一种改进的分治算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。
An improved divide and conquer algorithm for computing the convex hull of a finite set of points, which exclude the points impossible to be on the hull to reduce the time complexity when it searches the apexes of the convex hull, is presented. The correctness of the algorithm is proved strictly.
出处
《计算机工程与科学》
CSCD
2006年第8期63-65,共3页
Computer Engineering & Science
基金
湖南省自然科学基金资助项目(03JJY3099)
关键词
凸包
平面散点
分治法
FLOYD算法
convex hull
planar point set,divide and conquer algorithm
Floyd algorithm
