On K-Sets in Arrangements of Curves and Surfaces
On K-Sets in Arrangements of Curves and Surfaces
复制标题
关于曲线和曲面排列中的 K 集
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
M. Sharir
我们将K-集合和(≤k)-集合(见[3]、[12]和[19])的概念推广到曲线和曲面的排列。对于平面上的曲线，我们假设每条曲线都是简单的，并将平面分开。Ak点是被其他曲线(或被其他曲线限定的半平面)的精确yk内部覆盖的两条曲线的交点；k-集是这样排列的所有k-点的集合，(≤k)-集是所有j-集的并，对于J≤k，采用Clarkson和Shor[13]的概率分析技术，我们得到了(≤k)-集的最大尺寸与一条曲线样本的0-集的最大尺寸之间的下界。利用这类0-集的大小的已知界，我们在下列特殊情况下得到了(≤k)-集的最大大小的渐近紧界：(I)如果每对曲线至多相交两次，则最大大小为？(Nk？(Nk))。(Ii)如果曲线是无界圆弧，且每一对曲线至多相交三次，则其最大尺寸为？(Nk？(n/k))。(3)如果曲线单调圆弧及其每一对相交于至多某些固定点数，则(≤k)-集的最大长度为？(k2？S(Nk))，其中S(M)是(m，S)-Davenport-Schinzel序列的最大长度.我们还将这些结果推广到三维及更高维的某些曲面上。最后，我们给出了这些结果在线段和曲线的排列、高阶Voronoi图、平面上不相交凸集的部分戳等方面的各种应用。一个有趣的应用程序产生了ANDO(N LogN)，当它们以随机顺序堆叠在彼此的顶部时，在n个水平圆盘的排列中，垂直可见特征的期望数量受到限制。这进而导致对平面中的n个盘进行有效的随机化预处理，以便允许快速插入查询，其中我们想要报告包含查询点的所有盘。
We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is ?(nk?(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is ?(nk?(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is ?(k2?s(nk)), where ?s(m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point.