Geometric Computing

几何计算

• 批准号: RGPIN-2014-06399
• 负责人: Bose, Prosenjit
• 金额: $ 3.35万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612197
• 关键词: Geometric; Computing

My research area is Computational Geometry, a field devoted to the design and analysis of algorithms and data structures for geometric problems. My research focuses both on theoretical and practical issues. The geometric application areas I concentrate on include routing on geometric networks, geometric data structures, mesh generation/manipulation, graph drawing, visualization and pattern recognition. The main goal of my research has been and continues to be to bridge the gap between theoretical and practical efficiency by finding practical algorithmic solutions to applied geometric problems that have theoretical performance guarantees. Below, I provide a few examples of the type of geometric problems I am currently concentrating on. Communication between wireless devices has an inherent geometric component since these devices have a physical location which is constantly changing. Currently, I am applying my expertise in geometry to develop algorithms that take advantage of this geometric component resulting in more efficient and reliable communication between wireless devices. The problems in this area are particularly challenging since the network is dynamic, i.e. the wireless devices are usually moving. Moreover, this dynamic nature means that no single entity has complete knowledge of the whole network, requiring the development of algorithms that are online and use little memory. The standard method for modelling wireless networks is through the use of geometric graphs. A geometric graph is a graph where each vertex is a point in the plane (or possibly higher dimensions depending on the application) and an edge is a line segment or a curve joining two points. My research in this area focuses on the following themes: (1) How to route (i.e. find a path) efficiently in a geometric network, (2) How to construct geometric networks with certain desirable properties? Facility Location is an area where the main focus consists of placing one or more facilities in a region in a manner that optimizes certain criteria with respect to a set of clients. For example, in trying to decide where to build a new fire station in a city, one may want to place it somewhere that minimizes the response time to the target population. Facility Location problems are inherently geometric. Currently, I am studying several variants of this problem and trying to develop efficient solutions. A fundamental question in the manufacturing industry concerning every type of manufacturing process (such as NC-machining or casting) is: Given an object, can it be built using a particular process? I have successfully developed and applied computational geometry techniques to answer some basic problems of this type. Often it is geometric constraints that determine if an object can be built by a particular process. By modelling a process geometrically, we can determine if an object can be constructed at the design stage by determing if a CAD model of an object can be built by a particular manufacturing process. I plan to continue developing algorithms for answering these questions from a geometric perspective.

我的研究领域是计算几何，致力于几何问题的算法和数据结构的设计和分析领域。我的研究集中在理论和实践问题。我专注于几何应用领域，包括几何网络上的路由，几何数据结构，网格生成/操作，图形绘制，可视化和模式识别。我的研究的主要目标一直是，并将继续是弥合理论和实际效率之间的差距差距，找到实用的算法解决方案，应用几何问题，有理论性能保证。下面，我提供了几个我目前专注于的几何问题类型的例子。 无线设备之间的通信具有固有的几何分量，因为这些设备具有不断变化的物理位置。目前，我正在运用我在几何方面的专业知识来开发算法，利用这种几何组件，从而在无线设备之间实现更高效、更可靠的通信。由于网络是动态的，即无线设备通常是移动的，因此该领域中的问题特别具有挑战性。此外，这种动态性意味着没有一个实体对整个网络有完整的了解，这就需要开发在线且占用很少内存的算法。无线网络建模的标准方法是使用几何图形。几何图形是这样的图形，其中每个顶点是平面中的一个点（或者可能是更高的维度，取决于应用），并且边是连接两个点的线段或曲线。我在这一领域的研究主要集中在以下几个方面：（1）如何在几何网络中有效地路由（即找到路径），（2）如何构造具有某些期望性质的几何网络？ 设施选址是一个主要关注的领域，包括以优化一组客户的某些标准的方式在一个地区放置一个或多个设施。例如，在试图决定在城市中的哪里建立一个新的消防站时，人们可能希望将其放置在最小化目标人群响应时间的地方。设施选址问题本质上是几何问题。目前，我正在研究这个问题的几个变体，并试图开发有效的解决方案。 在制造业中，关于每一种制造工艺（如数控加工或铸造）的一个基本问题是：给定一个物体，它可以使用特定的工艺制造吗？我已经成功地开发和应用计算几何技术来回答这种类型的一些基本问题。通常是几何约束决定了一个对象是否可以通过特定的过程来构建。通过对过程进行几何建模，我们可以通过确定对象的CAD模型是否可以通过特定的制造过程构建来确定对象是否可以在设计阶段构建。我计划继续开发从几何角度回答这些问题的算法。