Matching points with rectangles and squares
Matching points with rectangles and squares
复制标题
矩形和正方形的匹配点
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
A. Wolff
中科院分区：
文献类型：
--
作者：
S. Bereg;Nikolaus Mutsanas;A. Wolff
在本文中，我们处理以下自然系列的几何匹配问题。给定几何对象的类 ${mathcal C}$ 和点集 P，${mathcal C}$ 匹配是一个集合 M$subseteq {mathcal C}$，使得每个 C ∈ M 恰好包含 P 的两个元素。如果匹配覆盖每个点，则匹配是完美的，如果对象不相交，则匹配是强的。我们专注于使用轴对齐的正方形和矩形来匹配点。我们给出了这些类的算法，并表明确定点集是否具有完美的强平方匹配是 NP 困难的。我们展示了我们的一个匹配算法解决了一系列地图标记问题。
In this paper we deal with the following natural family of geometric matching problems. Given a class ${mathcal C}$ of geometric objects and a point set P, a ${mathcal C}$-matching is a set M$subseteq {mathcal C}$ such that every C ∈ M contains exactly two elements of P. The matching is perfect if it covers every point, and strong if the objects do not intersect. We concentrate on matching points using axis-aligned squares and rectangles. We give algorithms for these classes and show that it is NP-hard to decide whether a point set has a perfect strong square matching. We show that one of our matching algorithms solves a family of map-labeling problems.