论文标题
使用正交对象的几何可分离性
Geometric Separability using Orthogonal Objects
论文作者
论文摘要
给定一个双重点集$ p = \ textbf {r} \ cup \ textbf {b} $ of红点和蓝点，分隔符是某种类型的对象，该对象将$ \ textbf {r} $和$ \ textbf {b} $分开。当分离器为a）固定取向的矩形环时，我们研究了几何可分离性问题b）任意取向的矩形环c）固定取向的平方环d）正交凸polygon。在本文中，我们给出多项式时间算法来构造上述每种类型的分离器，这些分离器也优化给定参数。
Given a bichromatic point set $P=\textbf{R} \cup \textbf{B}$ of red and blue points, a separator is an object of a certain type that separates $\textbf{R}$ and $\textbf{B}$. We study the geometric separability problem when the separator is a) rectangular annulus of fixed orientation b) rectangular annulus of arbitrary orientation c) square annulus of fixed orientation d) orthogonal convex polygon. In this paper, we give polynomial time algorithms to construct separators of each of the above type that also optimizes a given parameter.
