census.gov Notification
Due to the lapse of federal funding, portions of this website are not being updated. Any inquiries submitted via www.census.gov will not be answered until appropriations are enacted.

The Homeomorphism Extension Problem for Triangulations in Conflation

Written by:
RR86-03

Introduction

We discuss the problem of extending a one-to-one correspondence between two equinumerous finite sets of points in the plane to a homeomorphism between two topological spaces containing the sets. This problem arose during the development of a computer system to merge pairs of digitized map files at the Census Bureau. This system is called conflation. Conflation requires thee fundamental steps: control point selection, triangulation, and rubber-sheeting. Pairs of points, each pair consisting of a point from each map, are selected. The selected points of one map are then used as the vertices of a specific, well-defined triangulation on that map, and for each of the triangles of this triangulation we create a triangle on the corresponding set of verticles on the other map. The set of triangles on the second map need not form a triangulation there. If they do, we show that a specific extension of the correspondence between the vertices is a homeomorphism. Moreover, the converse is also true. Also, we prove a second characterization for triangulations from which an easy detection algorithm is derived. A description of related problems follows at the end.

Related Information


Page Last Revised - October 28, 2021