Abstract: We present a method for parameterizing irregularly triangulated input models over polyhedral domains with quadrilateral faces. A combination of center-based clustering techniques is used to generate a partition of the model into regions suitable for remeshing. Several issues are addressed: the size and shape of the regions, their positioning with respect to features of the input geometry, and the amount of distortion introduced by approximating each region with a coarse polygon. Region boundaries are used to define a coarse polygonal mesh which is quadrangulated to obtain a parameterization domain. Constraints can be optionally imposed to enforce a strict correspondence between input and output features. We use the parameterization for multiresolution Catmull-Clark remeshing and we illustrate two applications that take advantage of the resulting representation: interactive model editing and texture mapping.