NDLI: Joint triangulations and triangulation maps

Please wait, while we are loading the content...

Computing the link center of a simple polygon

Finding the visibility graph of a simple polygon in time proportional to its size

Jordan sorting via convex hulls of certain non-simple polygons

The weighted region problem

On the geodesic Voronoi diagram of point sites in a simple polygon

Optimal shortest path queries in a simple polygon

The all-geodesic furthest neighbor problem for simple polygons

Oriented projective geometry

Primitives for the manipulation of three-dimensional subdivisions

A graph based approach to object feature recognition

Polygon properties calculated from the vertex neighborhoods

Numerical stability of geometric algorithms

Discrete simulation of NC machining

Moving a ladder in three dimensions: upper and lower bounds

On detecting the orientation of polygons and polyhedra

Simplified Voronoi diagrams

An optimal O(n log n) algorithm for contour reconstruction from rays

Compliant motion planning with geometric models

On the number of faces in higher-dimensional Voronoi diagrams

Toughness and Delaunay triangulations

Joint triangulations and triangulation maps

Parallel processing for efficient subdivision search

Constrained Delaunay triangulations

An optimal algorithm for constructing the Delaunay triangulation of a set of line segments

A note on relative neighborhood graphs

Simultaneous containment of several polygons

Rectilinear shortest paths through polygonal obstacles in $O(n(logn)^{2})$ time

A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency

Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons

Fast algorithms for computing the largest empty rectangle

Variations on visibility

Algorithms for line transversals in space

Establishing order in planar subdivisions

Computing simple circuits from a set of line segments is NP-complete

Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension

Blending quadric surfaces with quadric and cubic surfaces

Analyzing surfaces: the truth about elimination theory

Joint triangulations and triangulation maps

Content Provider	ACM Digital Library
Author	Saalfeld, A.
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.
Starting Page	195
Ending Page	204
Page Count	10
File Format	PDF
ISBN	0897912314
DOI	10.1145/41958.41979
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-10-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Implementing data-dependent triangulations with higher order Delaunay triangulations

Quasi-greedy triangulations approximating the minimum weight triangulation

Lattice Triangulations How many triangulations exist for a 6 × 6 grid?

Implementing Data-Dependent Triangulations with Higher Order Delaunay Triangulations

Planar minimally rigid graphs and pseudo-triangulations

Optimal triangulations (1999).

Acute triangulations of pentagons.

On the computation of 3d periodic triangulations

A weight-coded genetic algorithm for the minimum weight triangulation problem

Joint triangulations and triangulation maps

Similar Documents

Implementing data-dependent triangulations with higher order Delaunay triangulations

Quasi-greedy triangulations approximating the minimum weight triangulation

Lattice Triangulations How many triangulations exist for a 6 × 6 grid?

Implementing Data-Dependent Triangulations with Higher Order Delaunay Triangulations

Planar minimally rigid graphs and pseudo-triangulations

Optimal triangulations (1999).

Acute triangulations of pentagons.

On the computation of 3d periodic triangulations

A weight-coded genetic algorithm for the minimum weight triangulation problem

Joint triangulations and triangulation maps