Partitioning arrangements of lines II: Applications
Partitioning arrangements of lines II: Applications
复制标题
线路分区布置二：应用
DOI：
--
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
P. Agarwal
中科院分区：
文献类型：
--
作者：
P. Agarwal
在本文中，我们提出了有效的确定性算法的各种问题，涉及线或段在平面上，使用分区算法中描述的同伴文件[A3]。这些应用包括：（i）一个O（m ~ 2/3 n ~ 2/3 ·log ~ 2/3 n· logω/3（m/n）+（m+n）logn）算法计算m个点与n条线的所有关联度，其中ω是一个<3.33的常数;（ii）一个O（m2/3 n2/3 ·log 5/3 n· logω/3（m/n）+（m+n）logn）算法计算n行排列的面;（iii）一个O（n ~ 4/3 log（ω+2）/3 n）算法计算一组n个线段的交点数;（iv）一个O（n4/3 log（ω + 2）/3 n）算法来计算两组段之间的“红-蓝”交叉点，（v）一个O（n ~ 3/2log ω/3 n）算法，用于计算n个点的低刺数生成树。本文还提出了一个算法，对于给定的平面上的n个点集，在时间O（n <$mlog ω+1/2n）内将其预处理成一个大小为O（m）（n logn≤m≤ n ~ 2）的数据结构，从而在O（（n/m）log ~ 3/2n）时间内计算出S中位于查询三角形内的点的个数.
In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m2/3n2/3 · log2/3n · logω/3 (m/√n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where ω is a constant <3.33; (ii) anO(m2/3n2/3 · log5/3n · logω/3 (m/√n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n4/3 log(ω+2)/3n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n4/3 log(ω + 2)/3n) algorithm to count “red-blue” intersections between two sets of segments, and (v) anO(n3/2 logω/3n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(n√m logω+1/2n), into a data structure of sizeO(m) forn logn≤m≤n2, so that the number of points ofS lying inside a query triangle can be computed inO((n/√m) log3/2n) time.