计算几何：随机增量式算法在点定位中的应用

"计算流体力学与传热学 陶文全 - 计算几何：算法与应用 邓俊辉译" 本文涉及的主题是计算几何，特别是计算流体力学与传热学中的算法应用。计算几何是一门结合了数学、计算机科学和工程学的学科，它研究如何用算法解决几何问题。陶文全和邓俊辉的工作可能涵盖了这一领域的多个方面，包括几何结构的变化、点定位算法、构形空间的分析以及算法效率的上界。 在描述中提到了随机增量式算法，这种算法常用于动态维护几何结构。定理9.14和9.15讨论了算法运行时几何结构变化量的上界和点定位计算量的上界。点定位是计算几何中的一个重要问题，它涉及到在给定几何结构中找到特定点的位置或属性。定理9.15给出了一个期望值的上界，这个上界与构形空间的最大度数d有关，且与算法生成的不同构形有关。 书中的内容可能涵盖以下几个部分： 1. 线段求交：这是计算几何的基本问题，用于找出一组线段的交点。专题图叠合和双向链接边表是解决这个问题的两种方法。 2. 多边形三角剖分：多边形的三角剖分在图形渲染和物理模拟中至关重要。看守与三角剖分的关系可能涉及到如何有效地构建和使用三角剖分来模拟观察者视线。 3. 线性规划：线性规划在几何优化问题中起到关键作用，如铸模制造中的几何形状优化。递增式线性规划和随机线性规划是解决这类问题的策略。 4. 正交区域查找：kd-树和区域树是数据结构，用于高效地在高维空间中执行查询，特别适用于数据库系统。 5. 点定位：点定位算法，如随机增量式算法，用于确定点在复杂几何结构中的位置。这部分还可能讨论了如何处理退化情况。 6. Voronoi图：Voronoi图是几何分割的一种，用于分析点集的邻近关系。线段集Voronoi图和最远点Voronoi图是其变体，分别对应不同的应用需求。 7. 排列与对偶：排列和对偶概念在光线跟踪和超采样等图形处理中有着重要应用，它们帮助理解和优化计算过程。 8. Delaunay三角剖分：虽然没有详细展开，但Delaunay三角剖分是计算几何中的另一个核心概念，用于构建无交叉的三角网格，常用于三维建模和模拟。 以上各个部分的讨论都与计算几何的理论和实践紧密相关，不仅提供了算法设计的基础，也为实际问题的解决提供了工具。通过邓俊辉的翻译，这些内容对中国读者来说更加易读和理解，有助于推进国内在计算几何领域的研究和教育。