Finding a minimum medial axis of a discrete shape is NP-hard

详细信息    查看全文

• 作者：David Coeurjolly ; Jé ; rô ; me Hulin ; Isabelle Sivignon
• 关键词：Minimum medial axis ; NP-completeness ; Bounded approximation algorithm
• 刊名：Theoretical Computer Science
• 出版年：2008
• 出版时间：28 October 2008
• 年：2008
• 卷：406
• 期：1-2
• 页码：72-79
• 全文大小：1385 K

文摘

The medial axis is a classical representation of digital objects widely used in many applications. However, such a set of balls may not be optimal: subsets of the medial axis may exist without changing the reversivility of the input shape representation. In this article, we first prove that finding a minimum medial axis is an NP-hard problem for the Euclidean distance. Then, we compare two algorithms which compute an approximation of the minimum medial axis, one of them providing bounded approximation results.