No Quadrangulation is Extremely Odd

Prosenjit Bose? Godfried Toussainty

Abstract

Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except possibly the outer face) is a quadrilateral. We show that S admits a quadrangulation if and only if S does not have an odd number of extreme points. If S admits a quadrangulation, we present an algorithm that computes a quadrangulation of S in O(n log n) time even in the presence of collinear points. If S does not admit a quadrangulation, then our algorithm can quadrangulate S with the addition of one extra point, which is optimal. We also provide an ?(n log n) time lower bound for the problem. Finally, our results imply that a k-angulation of a set of points can be achieved with the addition of at most k ? 3 extra points within the same time bound.

1 Introduction

Given a set of points in the plane, the problem of determining whether the set admits a certain combinatorial structure has received considerable attention. Of particular importance is the study of triangulations of point sets due to its many applications in graphics, medical imaging, Geographic Information Systems (GIS), finite element methods, statistics, scattered data interpolation, and pattern recognition to name a few ([1], [3], [24], [31], [35], [37], [38], [40]). However, in the study of finite element methods and scattered data interpolation, it has recently been shown that quadrangulations may be more desirable objects than triangulations. A quadrangulation of a set of points S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except possibly the outer face) is a quadrilateral.

A fundamental component of finite element methods is the automatic and semi-automatic generation of meshes for finite element analysis (see Ho-Le [15] for a survey of the area). The problem of converting a triangular mesh to a mesh consisting of quadrilaterals (quadrangular mesh) has been studied by Heighway [13] and Johnston et al. [16]. Johnston et al. integrate several heuristics into a system that automatically converts a triangular mesh into a quadrangular mesh which runs in O(n2) time and adds up to O(n) extra points to complete the quadrangulation where n is the size of the input. Such extra points are often referred to as Steiner points. deBerg [9] has devised a very simple algorithm that converts a triangular mesh to a quadrangular mesh with the addition of O(n) Steiner points (refer to Figure 1). Each triangle of the triangulation is decomposed into three quadrangles (quadrilaterals) using the following approach: place a Steiner point at the midpoint of each edge of the triangulation as well as in the center of each triangle of the triangulation. Then complete the quadrangulation by connecting the Steiner point in the center of each triangle to the three Steiner points on its edges.

?Research supported by a KILLAM and NSERC postdoctorate fellowship. Address: Department of Computer Science, University of British Columbia, 201 - 2366 Main Mall, Vancouver, British Columbia, V6T 1Z4. E-mail: [email protected]. yResearch supported by grants NSERC-OGP0009293 and FCAR-93ER0291. Address: School of Computer Science, McGill University, 3480 University, Montr?eal, Qu?ebec, H3A 2A7. E-mail: [email protected].