Improved Bounds for Planar k -Sets and Related Problems
Improved Bounds for Planar k -Sets and Related Problems
复制标题
平面 k 集和相关问题的改进界限
DOI：
--
复制
发表时间：
1998
影响因子：
0.8
通讯作者：
T. Dey
中科院分区：
文献类型：
--
作者：
T. Dey
抽象的。我们证明了针对平面k键的O（N（K+1）1/3）上限。这是大约27年前的早期解决方案后，这是对该界限的首次相当大的改进。我们的证明技术还适用于在线段的排列中提高k级组合复杂性的当前界限，n线结合的k凸音多边形，参数最小跨越树和一般参数矩阵。
<lsiheader>
<ininerpub> 1998年6月26日
<editor>主持人：＆lsilt; a href = ../edboard.html＃ceapects＆lsigt;
<PDFNAME> 19N3P373.pdf
<pdfexist>是
<htmlexist>否
<htmlfexist>否
<dexexist>是
<部分名称>
</lsiheader>
Abstract. We prove an O(n(k+1)1/3) upper bound for planar k -sets. This is the first considerable improvement on this bound after its early solution approximately 27 years ago. Our proof technique also applies to improve the current bounds on the combinatorial complexities of k -levels in the arrangement of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees, and parametric matroids in general.
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p373.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>