Joint triangulations and triangulation maps

ABSTRACT

In rubber-sheeting applications in cartography, it is useful to seek piecewise-linear homeomorphisms (PLH maps) between rectangular regions which map an arbitrary sequence of n points {p1, p2, …,pn} from the interior of one rectangle to a corresponding sequence {q1, q2, …, qn} of n points in the interior of the second region. This paper proves that it is always possible to find such PLH maps and describes then in terms of a joint triangulation of the domain and the range rectangular regions. One naive approach to finding a PLH map is to triangulate (in any fashion) the domain rectangle on its n points and four corners and to define a piecewise affine map on each triangle ▴p11p12p13 to be the unique affine map that sends the three vertices p11, p12, p13 of the triangle to the three corresponding vertices q11, q12, q13 of the image triangle ▴q11q12q13. Such piecewise affine maps send triangles to triangles, agree on shared edges, and thus extend globally, and will be called triangulation maps. The shortcoming of building transformations in this fashion is that the resulting triangulation map need not be one-to-one, although there is a simple test to determine if such a map is one-to-one (see Theorem 2 below). If the map is one-to-one, then the image triangles will form a triangulation of the range space; and we will have a joint triangulation. If the map is not one-to-one, then there will be folding over of triangles. It may be possible to alleviate this folding by choosing a different triangulation of the n domain points, or it may be the case that no triangulation of the n domain points will work. (See figures 5 and 6 below). We show that it will be possible, in all cases, to rectify the folding by adding appropriate additional triangulation vertex pairs {pn+1, pn+2, …, pn+m} and {qn+1, qn+2, …, qn+m} and retriangulating (see Theorem 1 below). This paper examines conditions for triangulation maps to be homeomorphisms and explores different ways of modifying triangulations and triangulation maps to make them joint triangulations and homeomorphisms. The paper concludes with a section on alternative constructive approaches to the open problem of finding joint triangulations on the original sequences of vertex pairs without augmenting those sequences of pairs. The existence proofs in this paper do not solve computational geometry problems per se; instead they permit us to formulate new computational geometry problems. The problems we pose are of interest to us because of a particular application in automated cartography.

REFERENCES

• 1: Corbett, J., 1979, TODOlO9iCal Princioles in Cartoaranhy, Technical Paper 48, Bureau of the Census, Washington, DC.
• 2: Goodman, J-E., and Pollack, R.. 1983. nRultidirensional Sorting." SIA?l J. Comat ., Vol 12, No. 3, pp. 484-507.
• 3: L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
• 4: Lefschetx, S., 1975. ADDliCatiOnS Of Alsebralc TODOlOaV, New York, NY, Springer-Verlag.
• 5: Mount, David, 1986, personal conmnunlcatlon, College Park, RD.
• 6: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 7: White, W.S. and P. Griffin, 1985, nPlecewlse Linear Rubber-Sheet Uap Transformation," The American Cartwraoher. vol 12-2. pp 123-131.
• 8: White, n. S., 1983, 'Tribulations of Automated Cartography and How Uathematics Helps": Auto-Cart0 Six, V. 1. PP. 408-418, Ottawa, Canada, 6th International Symposium on Automated ~rtogrsphY.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Theory