Algorithms for geometric reconstruction problems

几何重建问题的算法

• 批准号: 227718-2010
• 负责人: Biedl, Therese
• 金额: $ 1.46万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=546807
• 关键词: Algorithms; 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.

任何玩过纸笔拼图的人（比如数独、卡库罗、非图或桥牌）都解决了一个重建问题：给定一个物体的部分信息，根据它重建这个物体。我建议研究这样的重建问题，这不仅是谜题的动机，更重要的是许多医疗和工业应用。我的方法是从理论计算机科学的角度出发的。因此，主要问题是：“计算机能否在相当短的时间内解决这个重建问题？”如果是，那么目标就是找到最快的算法。如果没有，那么就需要启发式方法，我的目标是开发可以证明性能良好的启发式方法，至少在某些特殊情况下。