James Glimm.

A computational model for interfaces online

. (page 1 of 2)
Online LibraryJames GlimmA computational model for interfaces → online text (page 1 of 2)
Font size
QR-code for this ebook



C -
C -














Courant Mathematics and
Computing Laboratory

U.S. Department of Energy

A Computational Model for Interfaces

J. Glimm and O. A. McBryan

Research and Development Report

Supported by the Applied Mathematical Sciences
subprogram of the Office of Energy Research,
U.S. Department of Energy under
Contract DE-AC02-76ER03077

3 < Mathematics and Computers

lune 1985



Mathematics and Computers
c\1^ UC-3.

^ v&V^'^^^ ,> DOE/ER/03077-26:

^6t• 3. •♦. 5

Departmeat of Mathematics

Courant Institute

New York University

New York, NY 10012.


Decompositions of the plane into disjoint components
separated by airves occur frequently. We describe a package of
subroutines which provides facilities for defining, building and
modifying such decompositions and for efficiently solving vari-
ous point and area location'"|:flrbblei!fs."'"' " '""^

Beyond the point that the specification of this package may

be useful to others, we reach the broader conclusion that well

::c: 03 ,s:;~s-:;i.-.^;:' ... ^;:.

designed data structures and support routines allow the use of
more conceptual or non-numencal portions BONDS for a given block, then the
COMPONENT is uniquely defined, ^d; isvalso stored with the precomputed
data. This same data is used by the routine intersections for efficiency rea-

While this particular pre-processing mechanism appears adequate for
many problems, it is not optimal, either in computation time or storage
space. It is not difficult to replace the current code for component with other
pre-processing schemes. A crude point location algorithm is easily devised
based on comparison of location relative to all n BONDS of an INTERFACE,
and requires 0{n) computation time, but no pre-processing or extra storage.
The algorithm described here consumes 0{n) + 0{g~) storage and pre-
processing time when the superimposed grid has dimensions g by g. How-
ever the point location computation cost is then effectively 0(1) in n for typi-
cal interfaces we have encountered, although the worst case computation time
is still 0{n) - corresponding to the case where the complete interface is con-
tained in a single grid rectangle. For a review of the point location problem
and related areas in computational geometry we refer to several recent papers

- 10 r

in the computer science literature.^-''^'*'^^'^^ Future versions of this software
may well incorporate other approaches to point location. It is important to
stress that what is required is algorithms with good behavior on normal inter-
faces, even if their worst-case behavior is poor (eg close to linear).


Based on our experience with planar interfaces, we make here several
comments on the problem of defining data structures and support routines
for interfaces in higher space dimensions. We adopt the point of view of
computational continuum mechanics, where the interfaces designate material
boundaries, phase boundaries or discontinuous waves, but there are a number
of other and unrelated applications such as graphics for these ideas. An inter-
face in R" will consist of a number of smooth surfaces and their boundaries,
boundaries of boundaries etc. The smooth surfaces will in general have an
arbitrary topology, so that they cannot be parameterized by an open subset of
R^ or in other terminology, by a sfe^fii^ cobrdiiiate chart. The surfaces of
dimension j will in general share s6me ""common boundaries of dimension
;' - 1. Thus the data structure for a numerical description of an interface
will consist of a list of smooth surfaces of various diincnsions together with a
list of boundary relations among these surfaces. Each surface of dimension j
should include a pointer to the surfaces of dimension j + I which it bounds
and to the surfaces of dimension y — 1 in its boundary together with the rela-
tive orientation of these surfaces. We note that the boundary of an interface
of highest dimension j is an interface of highest dimension j - 1, so that for
the case n = 3, ; = 2, the boundaries are given by the data structures defined
in this paper, with the simple addition of an extra real variable z to the POEnT
data structure.

There are three requirements which determine the data structure for the
description of a single smooth surface in an interface. A small perturbation of
the points (such as would occur in a single time step of a time dependent evo-
lution) should not require a rrparameterization of the surface. Reparameteri-
zation, when required, should be a local operation and the local reparameteri-


Online LibraryJames GlimmA computational model for interfaces → online text (page 1 of 2)