Geometric Computing

几何计算

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

我的研究领域是计算几何，这是一个致力于设计和分析几何问题的算法和数据结构的领域。我的研究侧重于理论和实践问题。我关注的几何应用领域包括几何网络路由、几何数据结构、网格生成/操作、图形绘制、可视化和模式识别。我研究的主要目标一直是并将继续是通过寻找具有理论性能保证的应用几何问题的实用算法解决方案来弥合理论和实际效率之间的差距。下面，我将提供一些我目前正在关注的几何问题的例子。