摘要
Ａｇｇａｒｗａｌ指出Ｓｔｅｅｌｅ和Ｙａｏ的关于凸壳问题计算间下界的证明仅当点集是非退化时是有效的．至今还不清楚他们的证明是否可以经过修改后处理对凸壳问题的解集无任何约束的情形．在固定阶代数判定树模型下，本文彻底解决了这个问题．
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.
出处
《软件学报》
EI
CSCD
北大核心
1994年第12期38-43,共6页
Journal of Software
基金
国家教育委员会留学回国人员资助
