Algorithms for geometric reconstruction problems

点击翻译按钮获取中文摘要

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.