凸壳问题的计算时间下界
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家教育委员会留学回国人员资助


ON THE LOWER BOUND FOR CONVEX HULL PROBLEM
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

王晓东.凸壳问题的计算时间下界.软件学报,1994,5(12):38-43

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1991-12-21
  • 最后修改日期:1992-09-13
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号