论文标题
从一两个X射线中重建凸集
Reconstruction of Convex Sets from One or Two X-rays
论文作者
论文摘要
我们考虑了一类离散层析成像的问题，这些问题过去已经深入研究：从其水平和/或垂直X射线中重建了凸形晶格集，即从连续水平和垂直线的一系列点数中的点数。 HV-CONVEX多支着的重建通常分为两个步骤，首先是填充操作的填充步骤，其次是开关组件的凸聚集。我们证明了有关凸聚集步骤的三个结果：（1）用于重建HV-Convex多支克的凸聚集步骤并不总是提供解决方案。屈服于此结果的示例称为\ textit {the the bad Guy}，并反驳了域的猜想。 （2）仅在多项式时间内执行一个X射线设置的数字凸形晶格的重建。我们通过在有向的无环图中编码凸聚集问题来证明这一点。 （3）采用相同的策略，我们证明可以在多项式时间内求解从水平和垂直X射线的脂肪数字凸组的重建。脂肪是数字凸集的属性，该集合涉及左，右，顶部和底部的相对位置。不是脂肪的晶格集的重建的复杂性仍然是一个悬而未决的问题。
We consider a class of problems of Discrete Tomography which has been deeply investigated in the past: the reconstruction of convex lattice sets from their horizontal and/or vertical X-rays, i.e. from the number of points in a sequence of consecutive horizontal and vertical lines. The reconstruction of the HV-convex polyominoes works usually in two steps, first the filling step consisting in filling operations, second the convex aggregation of the switching components. We prove three results about the convex aggregation step: (1) The convex aggregation step used for the reconstruction of HV-convex polyominoes does not always provide a solution. The example yielding to this result is called \textit{the bad guy} and disproves a conjecture of the domain. (2) The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. (3) With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the lattice sets which are not fat remains an open question.
