Improved bounds on planar k-sets and k-levels
Improved bounds on planar k-sets and k-levels
复制标题
改进了平面 k 集和 k 水平的界限
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
T. Dey
中科院分区：
文献类型：
--
作者：
T. Dey
我们证明了平面k-集的一个O(nk/sup 1/3/)上界。这是自大约27年前的早期解决方案以来，对这一界限的第一次重大改进。我们的证明技术也适用于改善目前关于直线段排列中的k层、n线并中的k个凸多边形、参数最小生成树和参数拟阵的组合复杂性的界。
We prove an O(nk/sup 1/3/) upper bound for planar k-sets. This is the first considerable improvement on this bound after its early solutions approximately twenty seven years ago. Our proof technique also applies to improve the current bounds on the combinatorial complexities of k-levels in arrangements of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees and parametric matroids in general.