凸壳问题的计算时间下界

Ａｇｇａｒｗａｌ指出Ｓｔｅｅｌｅ和Ｙａｏ的关于凸壳问题计算间下界的证明仅当点集是非退化时是有效的．至今还不清楚他们的证明是否可以经过修改后处理对凸壳问题的解集无任何约束的情形．在固定阶代数判定树模型下，本文彻底解决了这个问题