Polygon Approximations of the Euclidean Circles on the Square Grid by Broadcasting Sequences
Haomin Song  1  , Igoer Potapov  1  
1 : University of Liverpool

Euclidean circle approximation on the square grid is an important problem in digital geometry. Recently several schemes have been proposed for approximation of Euclidean circles based on Neighbourhood Sequences, which correspond to repeated application of the von Neumann and Moore neighbourhoods on a square grid. In this paper we study polygon approximations of the Euclidean circles on the square grid with Broadcasting Sequences which can be seen as a generalization of Neighbourhood Sequences. The polygons generated by Broadcasting Sequences are the Minkowski sums of digital disks defined by a given set of broadcasting radii. We propose a polynomial time algorithm that can generate Broadcasting Sequences which are providing flexible and accurate approximation of Euclidean circles.


Online user: 1