Algorithms for geometric reconstruction problems

任何曾经玩过纸笔益智游戏的人(如数独、Kakuro、Nongraph或Bridges)都解决了重建问题：给出关于某个对象的一些部分信息，从它重建该对象。我建议研究这样的重建问题，这些问题不仅受到谜题的驱使，更重要的是受到许多医疗和工业应用的推动。我的方法是从理论计算机科学的角度出发。因此，主要的问题是：“这个重建问题能在合理的短时间内由计算机解决吗？”如果是，则目标是找到尽可能快的算法来做到这一点。如果不是，则需要启发式方法，我的目标是开发至少在某些特殊情况下表现良好的启发式方法。

Anyone who has ever played a pen-and-paper puzzle (such as Sudoku, Kakuro, Nonogram or Bridges) has solved a reconstruction problem: given some partial information about an object, reconstruct the object from it. I propose to study such reconstruction problems, which are motivated not only by puzzles, but more importantly by many medical and industrial applications. My approach is from a theoretical computer science point of view. Thus, the main question is: "Can this reconstruction problem be solved by a computer in reasonably short time?" If yes, then the goal is to find the fastest possible algorithm to do so. If no, then heuristics are required, and my goal is to develop heuristics that performs provably well, at least in some special cases.