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.

任何玩过纸笔谜题（例如数独、数独、Nonogram 或 Bridges）的人都已经解决了重建问题：给定有关对象的部分信息，从中重建该对象。 我建议研究此类重建问题，这不仅是出于谜题，更重要的是出于许多医学和工业应用的动机。 我的方法是从理论计算机科学的角度出发的。 因此，主要问题是：“计算机能否在相当短的时间内解决这个重建问题？” 如果是，那么目标是找到最快的算法来实现这一点。 如果不是，那么就需要启发式方法，我的目标是开发可证明性能良好的启发式方法，至少在某些特殊情况下如此。