Parallel Computational Geometry Algorithms and Implementations

并行计算几何算法和实现

• 批准号: 9102553
• 负责人: W Randolph Franklin
• 金额: $ 9.85万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-09-01 至 1994-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9102553&HistoricalAwards=false
• 关键词: Parallel; Computational; Geometry; Algorithms; Implementations

This project is concerned with parallel algorithms in computational geometry that will be efficient when applied to large, real, databases. The emphasis is on implementable algorithms instead of on algorithms with merely good theoretical asymptotic performance. Two major techniques to be used are uniform grids and local topological structures. The uniform grid allows efficient, easy, spatial coincidence determination. Local topological data structures allow the calculation of mass properties of a (well-defined) polyhedron without having any global topological information. This research will extend previous work in visible surface determination and Boolean combinations of polyhedra to higher level algorithms. These algorithms included determining mass properties of a constructive solid geometry tree, finding the tool-path volume and volume of material cut out by a numerically controlled drill, interference detection in robotics, and the cross-area problem in cartography. What these applications all have in common is the need to determine spatial coincidences in large databases and to find mass properties of Boolean combinations.

这个项目是关于并行算法在计算 当应用于大型的，真实的， 数据库。 重点是可实现的算法，而不是 算法仅仅具有良好的理论渐近性能。 两 采用的主要技术是均匀网格和局部网格 拓扑结构 均匀的网格允许高效，简单， 空间重合确定 局部拓扑数据结构 允许计算（定义明确的） 多面体，而不具有任何全局拓扑信息。 本研究将扩展前人在可见光表面的工作 多面体的确定和布尔组合 算法 这些算法包括确定 构造性立体几何树，查找刀具路径体积， 由数控钻头切割出的材料体积， 机器人中的干扰检测，以及机器人中的交叉区域问题。 地图学 这些应用程序的共同点是需要 在大型数据库中确定空间重合， 布尔组合的性质。