论文标题
曲线排列中的点位置
Point-Location in The Arrangement of Curves
论文作者
论文摘要
给出了飞机上$ n $曲线的布置。查询是一个点$ Q $，目标是找到包含$ Q $的安排的面孔。用于点位置的数据结构将曲线预处理成$ n $的多项式大小的数据结构，以便可以在$ n $中及时回答查询。 我们设计了一个数据结构，以求解点位置问题查询$ O（\ log c（n）+\ log s（n））$使用$ O（t（n）+s（n）+s（n）+s（n）\ log（s（n）））$预处理时间，如果总尺寸$ s（n）$ c（n）$ c（n）$ c（n）$ c（n）$ c（n）$ c（n）$ c（n）计算的时间$，计算每个细胞内部的曲线部分相对于细胞边界的至少一个段具有单调顺序。我们将这种分区称为曲线 - 超声酮多边形细分。
An arrangement of $n$ curves in the plane is given. The query is a point $q$ and the goal is to find the face of the arrangement that contains $q$. A data-structure for point-location, preprocesses the curves into a data structure of polynomial size in $n$, such that the queries can be answered in time polylogarithmic in $n$. We design a data structure for solving the point location problem queries in $O(\log C(n)+\log S(n))$ time using $O(T(n)+S(n)\log(S(n)))$ preprocessing time, if a polygonal subdivision of total size $S(n)$, with cell complexity at most $C(n)$ can be computed in time $T(n)$, such that the order of the parts of the curves inside each cell has a monotone order with respect to at least one segment of the boundary of the cell. We call such a partitioning a curve-monotone polygonal subdivision.
