Computational and Structural Advantages of Circular Boundary Representation

O. Aichholzer, F. Aurenhammer, T. Hackl, B. Juettler, M. Oberneder, and Z. Sir

Abstract:

Boundary approximation of planar shapes by circular arcs has quantitive and qualitative advantages compared to using straight-line segments. We demonstrate this by way of three basic and frequent computations on shapes - convex hull, decomposition, and medial axis. In particular, we propose a novel medial axis algorithm that beats existing methods in simplicity and practicality, and at the same time guarantees convergence to the medial axis of the original shape.

Reference: O. Aichholzer, F. Aurenhammer, T. Hackl, B. Juettler, M. Oberneder, and Z. Sir. Computational and structural advantages of circular boundary representation. In Proc. 10th Int. Workshop on Algorithms and Data Structures, WADS'07, Springer LNCS 4619, pages 374-385, Halifax, Canada, 2007.