| 摘要: |
| Ａｇｇａｒｗａｌ指出Ｓｔｅｅｌｅ和Ｙａｏ的关于凸壳问题计算间下界的证明仅当点集是非退化时是有效的．至今还不清楚他们的证明是否可以经过修改后处理对凸壳问题的解集无任何约束的情形．在固定阶代数判定树模型下，本文彻底解决了这个问题． |
| 关键词: 凸壳，计算时间下界 |
| DOI： |
| 分类号: |
| 基金项目:国家教育委员会留学回国人员资助 |
|
| ON THE LOWER BOUND FOR CONVEX HULL PROBLEM |
|
Wang Xiaodong
|
| Abstract: |
| As pointed out by A. Aggarwal the lower bound proof for convex hull problem of Steele and Yao is only positive when the points are not necessarily in general position. It is nuclear whether their proof can be modified to handle the case where there is no any restriction on the solution set of the problem. In the fixed-order algebraic-descision -tree model this paper solves the problem completely. |
| Key words: Convex hull, lower bound. |
