## Publication Details

*Algorithm 870: A Static Geometric Medial Axis Domain Decomposition in 2D Euclidean Space.*

Leonidas Linardakis and Nikos Chrisochoides.

Published in ACM Transactions on Mathematical Software, Article 4, 28 pages, Volume 34, No. 1, January, 2008

Abstract

We present a geometric domain decomposition method and its implementation, which produces good domain decompositions in terms of three basic criteria: (1) The boundary of the subdomains create good angles, i.e., angles no smaller than a given tolerance Phi_0, where the value of Phi_0 is determined by the application which will use the domain decomposition. (2) The size of the separator should be relatively small compared to the area of the subdomains. (3) The maximum area of the subdomains should be close to the average subdomain area. The domain decomposition method uses an approximation of a Medial Axis as an auxiliary structure for constructing the boundary of the subdomains (separators). The N-way decomposition is based on the “divide and conquer” algorithmic paradigm and on a smoothing procedure that eliminates the creation of any new artifacts in the subdomains. This approach is produces well shaped uniform and graded domain decompositions, which are suitable for parallel mesh generation