• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Balanced Partitioning of Polygonal Domains.
【24h】

Balanced Partitioning of Polygonal Domains.

机译：多边形域的平衡分区。

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

摘要

We study partitioning problems of polygonal domains under requirements of balancing various objective functions. Some of them are specific to Air Traffic Management, but others are more general and have a broader range of applications.;In Chapter 2 we start with a Districting problem, where we are given a partition of a polygon into weighted polygonal subdistricts, and are asked to merge them into a given number of districts while balancing their weights. We consider the problem in 1D and 2D, and the static and dynamic versions of the problem. We show that in 1 D this problem is polynomially solvable, and becomes NP-complete in 2D. We give approximation algorithms for several special cases of the problem.;In Chapter 3 we study the Airspace Sectorization problem, where the goal is to find a sectorization, i.e., a partition of the airspace into sectors, under a number of requirements on the geometry of the sectors, as well as on the air traffic flow-conformance, while balancing the controllers' workload. In Chapter 4 we propose a Local Redesigning Method (LRM), a heuristic that rebalances a given disbalanced sectorization by applying small local adjustments to the sectors boundaries. We evaluate LRM experimentally on synthetically generated scenarios as well as on the real historical traffic data and demonstrate that the sectorizations produced by our method are superior in comparison with the current sectorizations of the US airspace.;In Chapter 5 we propose a point-balancing convex polygonal partitioning problem defined in the following way: Given a polygon and a set of points in it, partition the polygon into the minimum number of convex pieces having a limited number of points in each piece. We present two optimal algorithms for the case of a simple polygon with some restrictions on the partitioning cuts. We also give a number of approximation algorithms for different variations of the problem.
机译：我们在平衡各种目标函数的要求下研究了多边形域的划分问题。其中一些特定于空中交通管理，而另一些则更通用，并且具有更广泛的应用。在第二章中，我们从分区问题开始，在该问题中，我们将多边形划分为加权的多边形分区，并且要求将它们合并到给定数量的区域中，同时平衡其权重。我们考虑一维和二维问题，以及问题的静态和动态版本。我们表明，在1D中，该问题可以多项式求解，并且在2D中变为NP完全。我们为问题的几种特殊情况提供了近似算法。在第3章中，我们研究了空域扇区化问题，其目的是在几何学上的许多要求下找到一个扇区化，即将空域划分为多个扇区部门以及空中交通流的一致性，同时平衡管制员的工作量。在第4章中，我们提出了一种局部重新设计方法（LRM），一种启发式方法，通过对扇区边界进行小的局部调整来重新平衡给定的不平衡扇区。我们在综合生成的场景以及实际历史流量数据上对LRM进行了实验评估，并证明了与美国空域的当前扇区划分相比，我们的方法产生的扇区划分更胜一筹。在第5章中，我们提出了点平衡凸多边形划分问题按以下方式定义：给定一个多边形和其中的一组点，将多边形划分为最少数量的凸块，每块凸块中的点数有限。对于一个简单的多边形，在分割切口上有一些限制，我们提出了两种最佳算法。我们还针对问题的不同变化提供了多种近似算法。

著录项

  • 作者

    Kostitsyna, Irina.;

  • 作者单位

    State University of New York at Stony Brook.;

  • 授予单位 State University of New York at Stony Brook.;
  • 学科 Computer Science.
  • 学位 Ph.D.
  • 年度 2013
  • 页码 95 p.
  • 总页数 95
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号