Geometric complexity
Geometric complexity
复制标题
DOI：
10.1145/800116.803772
复制
发表时间：
1975-05
期刊：
影响因子：
--
通讯作者：
M. Shamos
中科院分区：
文献类型：
--
作者：
M. Shamos
研究了计算几何中一些基本问题的复杂性，提出并分析了一些新的快速算法。给出了求解几何复杂性问题的一般方法，并给出了平面上涉及点、线、多边形集合的问题的上下界。努力将经典定理转化为有用的计算形式，并在欧几里得几何中的构造性问题和现代计算复杂性中的可计算性问题之间建立了类比。
The complexity of a number of fundamental problems in computational geometry is examined and a number of new fast algorithms are presented and analyzed. General methods for obtaining results in geometric complexity are given and upper and lower bounds are obtained for problems involving sets of points, lines, and polygons in the plane. An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.