Computation of Geometric Properties from the Medial Axis Transform in 0 (n logn) Time.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
The digital medial axis transfer MAT represents and image subset S as the union of maximal upright squares contained in S. Brute-force algorithms for computing geometric properties of S from its MAT require time O sq n, where n is the number of squares. Over the past few years, however, algorithms have been developed that compute properties for a union of upright rectangles in time O n log n, which makes the use of the MAT much more attractive. This document reviews these algorithms and also present efficient algorithms for computing union-of-rectangle representations of derived sets union, intersection, complement and for conversion between the union of rectangles and other representations of a subset. Author
- Theoretical Mathematics