Dynamic Minimum Length Polygon
| 详细信息 | 推荐本文 | |
- 作者：Jacques-Olivier Lachaud (1) jacques-olivier.lachaud@univ-savoie.fr
Xavier Proven莽al (1) xavier.provencal@univ-savoie.fr - 刊名：Lecture Notes in Computer Science
- 出版时间：2011
- 出版年：2011
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：6636
- 期：1
- 页码：208-221
- 数据来源：sp
摘要
This paper presents a formal framework for representing all reversible polygonalizations of a digital contour (i.e. the boundary of a digital object). Within these polygonal approximations, a set of local operations is defined with given properties, e.g., decreasing the total length of the polygon or diminishing the number of quadrant changes. We show that, whatever the starting reversible polygonal approximation, iterating these operations leads to a specific polygon: the Minimum Length Polygon. This object is thus the natural representative for the whole class of reversible polygonal approximations of a digital contour. Since all presented operations are local, we obtain the first dynamic algorithm for computing the MLP. This gives us a sublinear time algorithm for computing the MLP of a contour, when the MLP of a slightly different contour is known.