• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>World Multiconference on Systemics, Cybernetics and Informatics and 5th International Conference on Information Systems Analysis and Synthesis Vol.5: Computer Science and Engineering, Jul 31-Aug 4, 1999, Orlando, Florida >Drawing Constrained Rectangles in the Plane without Intersections
【24h】

Drawing Constrained Rectangles in the Plane without Intersections

机译：在没有相交的平面中绘制约束矩形

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper is devoted to study a particular case of the general problem known as Labeling. We want to draw rectangles in the plane in such a way that between any pair of them either one rectangle is contained in the other or both are disjoint. For each one of these rectangles a set of three points is given, such that k of them are corners of the rectangle and the other 3 - k points are in its sides. We prove that if k = 2 or 3 then the problem is solvable in polynomial time and it is NP-complete for k = 1.
机译：本文致力于研究称为标签的一般问题的特定案例。我们想要在平面中绘制矩形，使得在任何一对矩形之间包含一个矩形，或者两个矩形不相交。对于这些矩形中的每个矩形，给出了三个点的集合，这样它们中的k个是矩形的角，而其他3-k个点在其侧面。我们证明如果k = 2或3，则问题可以在多项式时间内解决，并且对于k = 1，它是NP完全的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号