Improved bounds on planar k-sets and k-levels

被引：13

作者：

Dey, TK ^{[1
]}

机构：

[1] Indian Inst Technol, Dept Comp Sci & Engn, Kharagpur 721302, W Bengal, India

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646104

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove an O(nk(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.

引用

页码：156 / 161

页数：6