计算几何：凸包算法与退化情况分析

"陶文全的《计算流体力学与传热学》讲解了计算几何中的核心概念，包括凸包的构建、算法复杂度分析、退化情况处理以及计算几何在实际应用中的挑战。书中通过SLOWCONVEXHULL算法展示了如何构建凸包，并分析了其O(n^3)的时间复杂度，指出在处理大规模数据时的不足，并引出了对更高效算法的需求。同时，讨论了多点共线的退化情况，这是计算几何中需要考虑的特殊情形。此外，书中还涵盖了线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图以及排列与对偶等重要主题，这些内容广泛应用于各种领域，如数据库查询、光线跟踪等。" 《计算几何——算法与应用》一书，作者Mark de Berg等人，由邓俊辉翻译，清华大学出版社出版，深入探讨了计算几何的各种算法和技术。书中不仅介绍了如何构建凸包，还涉及线段求交的专题图叠合、多边形三角剖分、线性规划、正交区域查找、点定位问题，以及Voronoi图和排列与对偶的概念。每个主题下都有详细的算法解析、实例演示、复杂度分析和习题，帮助读者理解和掌握计算几何的核心思想和方法。 例如，线段求交问题通过专题图叠合算法来解决，可以有效地计算线段间的交点。多边形三角剖分章节则讲解了如何将多边形划分为一系列三角形，这对于图形渲染和三维建模至关重要。线性规划章节不仅介绍了半平面求交，还讨论了递增式线性规划和无界问题的解决方案，这些都是优化问题的基础工具。 此外，正交区域查找和点定位问题涉及到数据结构如kd-树和区域树，这些数据结构在数据库查询和高维空间索引中扮演重要角色。Voronoi图的构建和应用，如邮局选址问题，展示了如何寻找最优布局以覆盖最大范围。排列与对偶的概念在光线追踪和超采样中有着重要应用，帮助处理图形渲染中的精度和效率问题。 这些资源提供了计算几何的全面学习路径，涵盖理论基础、算法实现和实际应用，适合对计算几何感兴趣的读者深入学习。