Approximation Algorithms in Computational Geometry

本计画探讨计算几何中的近似演算法， 两个问题：多面体曲面造型和欧氏 最短路径 在曲面造型中，人们试图构造多面体模型 基于一组无序采样点的复杂曲面。 的 构建和操作模型的复杂性 取决于它的顶点和面的数量，因此是一个自然的优化目标 最小化模型中的这些特征，而不超过预先指定的 误差容限 该项目研究了各种表面建模问题， 计算几何的形式化框架，并分析了计算几何中存在的问题 计算复杂性。 计算最短路径的问题是 机器人和自主导航的核心。研究调查了 最短路径问题的近似算法 和三维空间。 在两个维度中， 研究了最短路径问题：对一组多边形障碍物进行预处理， 给定两点p和q，可以确定它们之间的距离。 在多对数时间内。 在三维中，目标是设计更简单， 最短路径精确算法的更实用的替代方案 在多面体固体中或在多面体表面上。

This project investigates the topic of approximation algorithms in computational geometry, with focus on the two problems: polyhedral surface modeling and Euclidean shortest paths. In surface modeling, one tries to construct a polyhedral model of a complex surface, based on a set of unordered sample points. The complexity of constructing and manipulating the model depends on its number of vertices and faces, and therefore a natural optimization goal is to minimize these features in the model without exceeding a pre-specified error tolerance. The project studies various surface-modeling problems within the formal framework of computational geometry, and analyzes the issues of computational complexity. The problem of computing shortest paths is central to robotics and autonomous navigation. The research investigates approximation algorithms for shortest path problems in two and three dimensions. In two dimensions, the query version of the shortest path problem is studied: preprocess a set of polygonal obstacles so that given two points p and q, the distance between them can be determined in polylogarithmic time. In three dimensions, the goal is to design simpler and more practical alternatives to the exact algorithms for shortest paths among polyhedral solids or on a polyhedral surface.