• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Space-Efficient Algorithm for Finding the Connected Components of Rectangles in the Plane
【24h】

Space-Efficient Algorithm for Finding the Connected Components of Rectangles in the Plane

机译：求平面中矩形连通分量的空间有效算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An algorithm is presented for determining the connectivity of a set of N rectangles in the plane, a problem central to avoiding aliasing in VLSI design rule checkers. Previous algorithms for this problem either worked slowly with a small amount of primary memory space, or worked quickly but used more space. Our algorithm uses O(W) primary memory space, where W, the scan width, is the maximum number of rectangles to cross any vertical cut. The algorithm runs in O(N 1g N) time and requires no more than O(N) transfers between primary and secondary memory. Keywords: Very large scale integration; Computational geometry; Design rule checking; Algorithms; Rectangles; Connected components; Scanning.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号