论文标题
在3D中划分轴并行线
Partitioning axis-parallel lines in 3D
论文作者
论文摘要
令$ l $为$ \ mathbb {r}^3 $中的$ n $ axis-parallel行。我们对三个飞机的$ h $ $ \ mathbb {r}^3 $的分区感兴趣，以使得每个安排中的每个开放单元$ \ nathcal {a}（h）$与$ l $的几行相交。我们根据我们允许的分裂平面的类型来研究这种分区。我们获得以下结果。 $ \ bullet $有$ n $ n $ axis-axis-parallel行的集合，这样，对于任何三个拆分平面的$ h $，$ \ m m i \ m m i \ mathcal {a}（h）$中都有一个开放单元，至少相交〜$ \ $ \ lfloor n/3 \ rfloor n/3 \ rfloor-rfloor-1 \ of \ freac \ freac \ freac \ freac \ freac \ freac \ freac \ freac {1} n $ {1} n $} $\bullet$ If we require the splitting planes to be axis-parallel, then there are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least $\frac{3}{2}\lfloor n/4 \rfloor -1 \approx \ left（\ frac {1} {3}+\ frac {1} {24} \ right）n $ lines。此外，对于任何集合$ n $ n $ axis-axis-parallel行的$ l $，都存在三个$ h $的三个轴平行拆分平面，以使每个开放单元$ \ nathcal {a}（h）$在最多$ \ frac {7} \ frac {1} {3}+\ frac {1} {18} \ right）n $ lines。 $ \ bullet $对于任何集合的$ n $ axis-axis-Parallel行，存在三个轴平行和相互正交的拆分平面的$ h $，以便每个开放单元$ \ nathcal {a} a}（a}（h）$相交的$ \ mathcal {A} \ frac {1} {3}+\ frac {1} {12} \ right）n $ lines。
Let $L$ be a set of $n$ axis-parallel lines in $\mathbb{R}^3$. We are are interested in partitions of $\mathbb{R}^3$ by a set $H$ of three planes such that each open cell in the arrangement $\mathcal{A}(H)$ is intersected by as few lines from $L$ as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. $\bullet$ There are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least~$\lfloor n/3 \rfloor-1 \approx \frac{1}{3}n$ lines. $\bullet$ If we require the splitting planes to be axis-parallel, then there are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least $\frac{3}{2}\lfloor n/4 \rfloor -1 \approx \left( \frac{1}{3}+\frac{1}{24}\right) n$ lines. Furthermore, for any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel splitting planes such that each open cell in $\mathcal{A}(H)$ intersects at most $\frac{7}{18} n = \left( \frac{1}{3}+\frac{1}{18}\right) n$ lines. $\bullet$ For any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in $\mathcal{A}(H)$ intersects at most $\lceil \frac{5}{12} n \rceil \approx \left( \frac{1}{3}+\frac{1}{12}\right) n$ lines.
