首页> 外文会议>Computing and combinatorics >Largest Area Convex Hull of Axis-Aligned Squares Based on Imprecise Data
【24h】

Largest Area Convex Hull of Axis-Aligned Squares Based on Imprecise Data

机译:基于不精确数据的轴对齐正方形的最大面积凸包

获取原文
获取原文并翻译 | 示例

摘要

Data collected from real world are often imprecise. A few algorithms were proposed recently to compute the convex hull of maximum area when the axis-aligned squares model is used to represent imprecise input data. If squares are non-overlapping and of different sizes, the time complexity of the best known algorithm is O(n~7). If squares are allowed to overlap but have the same size, the time complexity of the best known algorithm is O(n~5). In this paper, we improve both bounds by a quadratic factor, i.e., to O(n~5) and O(n~3), respectively.
机译:从真实世界收集的数据通常不准确。最近提出了一些算法,当使用轴对齐的正方形模型表示不精确的输入数据时,可以计算最大面积的凸包。如果正方形不重叠且大小不同,则最著名算法的时间复杂度为O(n〜7)。如果允许正方形重叠但大小相同,则最著名算法的时间复杂度为O(n〜5)。在本文中,我们将二次边界的二次因子分别提高到O(n〜5)和O(n〜3)。

著录项

  • 来源
    《Computing and combinatorics》|2011年|p.192-203|共12页
  • 会议地点 Dallas TX(US);Dallas TX(US)
  • 作者单位

    Department of Computer Science, University of Texas at Dallas, USA;

    Institute of Computing Technology, Chinese Academy of Sciences, China,Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China;

    Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China;

    Department of Computer Science, Montana State University, USA;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号