Tight Bounds for Visibility Matching of f-Equal Width Objects
Tight Bounds for Visibility Matching of f-Equal Width Objects
复制标题
f 等宽对象的可见性匹配的严格界限
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Rappaport
中科院分区：
文献类型：
--
作者：
D. Rappaport
设s表示r2中的紧凸物体。s的f宽度是s的两条不同的平行线与方向f之间的垂直距离。如果存在一个方向f使得每一对物体都具有相等的f宽度，则r2中一组不相交的凸紧物体具有相等的f宽度。对于一组f宽度相等的对象，可见性匹配是使用该集合的可见性图中站点的非交叉线进行匹配。在本文中，我们通过表明[2n/3]≤h(n)≤2n/3，建立了一组f等宽度对象的最大可见性匹配大小的严格界限。
Let s denote a compact convex object in R 2 . The f-width of s is the perpendicular distance between two distinct parallel lines of support of s with direction f. A set of disjoint convex compact objects in R 2 is of equal f-width if there exists a direction f such that every pair of objects have equal f-width. A visibility matching, for a set of equal f-width objects is a matching using non-crossing lines of site in the visibility graph of the set. In this note we establish tight bounds on the size of a maximal visibility matching for a set of f-equal width objects by showing that [2n/3] ≤ h(n) ≤ 2n/3.