Triangulation on Reconfigurable Meshes: A Natural Decomposition Approach

Central to many algorithms for reconfigurable meshes (R-meshes) is the method of divide-and-conquer (DAC). Although there is no provision in this method per se that a problem must be divided into subproblems evenly in size, in practice almost all existing DAC-based R-mesh algorithms divide problems in this fashion. This paper demonstrates that dividing a problem evenly is not necessarily a good approach. For some problems, a natural decomposition scheme may be preferable, in which a problem is divided into subproblems along their "natural" boundaries, often resulting in an irregular decomposition. Taking this approach, we obtain a new R-mesh algorithm that triangulates a set of points on O(1) time. This algorithm is simpler than existing ones. We also obtain an R-mesh algorithm for simple-polygon triangulation, the first such algorithm for this problem.