平面点集凸壳的实时算法

被引：13

作者：

周之英

机构：

[1] 清华大学

来源：

计算机学报 | 1985年 / 02期

关键词：

实时算法; 顶点数; 计算复杂度; 内点; 凸壳; 平面点集;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

本文提出平面点集凸壳的实时算法。该算法利用平衡二叉树来代表凸壳的顶点序列,使每次更新凸壳所需计算复杂度为O(log m)。因而n个点的凸壳的计算复杂度为O(n log m),空间复杂度为O(log m),当点服从均匀分布时,算法期望的计算复杂度为O(n)。

引用

收藏

页码：136 / 143

页数：8

相关论文

共 1 条

[1]

über die konvexe Hülle von n zuf?llig gew?hlten Punkten[J] . A. Rényi,R. Sulanke.Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete . 1963 (1)