Convex transversals
Convex transversals
复制标题
凸横
DOI：
10.1016/j.comgeo.2012.10.009
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Shang Yang
中科院分区：
文献类型：
--
作者：
Esther M. Arkin;Claudia Dieckmann;Christian Knauer;Joseph S.B. Mitchell;Valentin Polishchuk;Lena Schlipf;Shang Yang
我们回答了最初由Arik Tamir在第四届纽约大学计算几何日（1987年3月）提出的问题：“给定一个紧致集的集合，可以在多项式时间内决定是否存在一个凸体，其边界与集合中的每个集合相交？”证明了当集合是平面上的线段时，判定凸刺子的存在性是NP-困难的。如果集合是凸多边形的缩放副本，则问题仍然是NP难的。我们还表明，在3D的刺伤问题是很难时，集球。在积极的一面，我们给出了一个多项式时间算法来寻找最大数目的两两不相交段的凸断面（或凸多边形）在2D中，如果截线的顶点被限制到给定的点集。我们还考虑用正多边形的顶点刺-一个与近似对称检测密切相关的问题：给定平面上的一组圆盘，是否有可能在每个圆盘上找到一个点，使得这些点是正多边形的顶点？我们证明了该问题可以在多项式时间内求解，并给出了该问题的优化版本的算法。
We answer the question initially posed by Arik Tamir at the Fourth NYU Computational Geometry Day (March, 1987): “Given a collection of compact sets, can one decide in polynomial time whether there exists a convex body whose boundary intersects every set in the collection?”We prove that when the sets are segments in the plane, deciding existence of the convex stabber is NP-hard. The problem remains NP-hard if the sets are scaled copies of a convex polygon. We also show that in 3D the stabbing problem is hard when the sets are balls. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments (or convex polygons) in 2D if the vertices of the transversal are restricted to a given set of points.We also consider stabbing with vertices of a regular polygon – a problem closely related to approximate symmetry detection: Given a set of disks in the plane, is it possible to find a point per disk so that the points are vertices of a regular polygon? We show that the problem can be solved in polynomial time, and give an algorithm for an optimization version of the problem.
动态图算法的平均情况分析
影响因子：
1.1
作者：
David Alberts;Monika Henzinger
通讯作者：
Monika Henzinger
R3 中凸多面体的线横截面
DOI：
10.1137/080744694
发表时间：
2009
期刊：
Comput. Vis. Graph. Image Process.
影响因子：
--
作者：
Haim Kaplan;Natan Rubin;M. Sharir
通讯作者：
M. Sharir