научная статья по теме DISCRETE EXTRINSIC CURVATURES AND APPROXIMATION OF SURFACES BY POLAR POLYHEDRA Математика

Текст научной статьи на тему «DISCRETE EXTRINSIC CURVATURES AND APPROXIMATION OF SURFACES BY POLAR POLYHEDRA»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2010, том 50, № 1, с. 71-98

УДК 519.53

DISCRETE EXTRINSIC CURVATURES AND APPROXIMATION OF SURFACES BY POLAR POLYHEDRA1

© 2010 V. A. Garanzha

(119333 Moscow, ul. Vavilova, 40, Dorodnicyn Computing Center, RAS) e-mail: garan@ccas.ru Received November 28, 2008

Duality principle for approximation of geometrical objects (also known as Eudoxus exhaustion method) was extended and perfected by Archimedes in his famous tractate "Measurement of circle". The main idea of the approximation method by Archimedes is to construct a sequence of pairs of inscribed and circumscribed polygons (polyhedra) which approximate curvilinear convex body. This sequence allows to approximate length of curve, as well as area and volume of the bodies and to obtain error estimates for approximation. In this work it is shown that a sequence of pairs of locally polar polyhedra allows to construct piecewise-affine approximation to spherical Gauss map, to construct convergent point-wise approximations to mean and Gauss curvature, as well as to obtain natural discretizations of bending energies. Suggested approach can be applied to nonconvex surfaces and in the case of multiple dimensions.

Key words: polar polyhedra, discrete curvatures, DC surfaces (representable as a difference of convex functions), bending energy.

В.А. Гаранжа. Дискретные внешние кривизны и аппроксимация поверхностей полярными многогранниками. Принцип двойственности для аппроксимации тел многогранниками, известный также как метод исчерпывания Евдокса, был развит Архимедом в знаменитом трактате "Об измерении круга". Основная идея принципа двойственности состоит в построении пар вписанных и описанных многоугольников (или многогранников, в зависимости от размерности), которые аппроксимируют выпуклое тело. Такая последовательность позволяет приблизить объемы тел и площади их границ, и получить оценки ошибок аппроксимации. В данной работе показано, что последовательность пар локально полярных многогранников позволяет строить сходящиеся кусочно-аффинные аппроксимации сферического (гауссова) отображения поверхности, а также строить поточечные аппроксимации средней и гауссовой кривизны и естественные аппроксимации энергий изгибания поверхности. Предложенный подход обобщается на случай невыпуклых тел и на многомерный случай. Библ. 31. Фиг. 27.

Ключевые слова: полярные многогранники, дискретные кривизны, поверхности ПРВ (пред-ставимые как разность выпуклых функций), энергии изгибания.

1. LEGENDRE TRANSFORM AND POLAR POLYHEDRA Let us consider twice continuously differentiable function u(x) of d real variables

u = u(x) = u(x...,xd) and introduce new variablesp = p1, ...,pdusing relation

Pi = d u / dxj. (1)

Suppose that Hessian matrix of the function u is not degenerate. Then using equation (1) one can express at least locally Xj as functions ofp1, ..., pd.

Research supported by grant OMN-03 of Department of mathematical sciences, Russian Academy of Sciences, by program " Leading Scientific Schools" (project no. NSh-5073.2008.1) and by grant RFBR 09-01-12106-ofi-m.

Текст доклада, представленного на Международной конференции "Numerical geometry, grid generation and scientific computing", Москва, ВЦ РАН, 10-13 июня 2008 г.

Let us define new function u* via

u* = xp - u(x). (2)

Substituting function x(p) into (2) one can derive

u* = u*(pi, ...,pd). Let us express variation of function u* via variations of variables p .

du*

8u* = Z-8Pi = l,(Xi8p, + pi8xi) - 8u =

dpi

= El*,8Pi + (pi- ^)8xi

For completion of this expression one should express variations of x via variation ofp. This task is greatly simplified by the fact that due to equality (1) coefficients multiplying 8x; are equal to zero. Hence we derive

x, = du */dpj. (3)

This equality illustrates remarkable duality of the Legendre transform which can be expressed by the following diagram [1]

Primal system Dual system Variables x1; ..., xd px, ...,pd

Functions u = u(x1, ..., xd) u* = u*(p1, .,pd).

Transform

d u du* pi = — x, =-

dxi dpt

u* = xTp - u (x) u = xp - u *(p)

u* = u*(px,..., pd) u = u(xh..., xd)

H.. = iLä-, H = (H*)-1 H* = , H* = H-

8xixJ dpp.

Thus, new variables are partial derivatives of primal function with respect to primal variables, and vice versa. Hessian matrices for primal and dual functions are mutually inverse. One can see that transform defined by (4) is symmetric.

Of course, above considerations are not rigorous, because, for example, one cannot guarantee that nonlinear systems of equations (1), (3) are uniquely solvable.

Suppose now that function u(x) is strictly convex. Then equality u*(p) = xTp — u(x), where x is expressed as a function ofp using equality pi = du/dxi can be obtained as the solution of the maximization problem

u* (p) = max{ xp - u (x)}

x

Since function xTp — u(x) is strictly concave, its maximum is attained in a single stationary point = du/dx. These arguments explain the idea of rigorous formulation of the Legendre transform suggested by Fenchel [18].

Definition 1 (Legendre stransform). Consider function u : [R —- [R with closed epigraph. Legendre transform of u is given by relation

u*(x*) = sup {xTx* - u(x)}, (5)

(4)

d

x e R

where function u*(x*) is called dual function (or polar function).

Fig. 1. Polar correspondence between pointp and plane П.

The following theorem shows when the generalized Legendre transform formulation can be reduced to the original one.

Theorem 1 (see [2]). (a) Let function u e C^R ) be convex and finite. Then

u (x) + u* (Vu (x)) = xTV u (x); (b) if function u is strictly convex and if

lim ^^ = +да, Ы ^ » |x|

then u* e Cx(Rd). Moreover, if u e Cx(Rd) and

u(x)+ w*(x*) = xTx*,

then

x * = V u (x), x = Vu *(x *).

Geometric interpretation of Legendre transform. In order to explain geometric meaning of the Legend-

re transform, one has to recall the relation of polarity in projective geometry [20]. Consider pointp e R

and nondegenerate (d — 1)-dimensional quadric surface P in R . Suppose that one can draw from pointp rays touching surface P which is shown in Fig. 1. If quadric is defined by generic equation

ф^) = 0, ф^) = 1 x Ax + bTx + c,

where A is d x d matrix, then any touching point is the solution of the system

(У -P)TVф(y) = 0, ф( У) = 0

or

y Ay + by - p TAy - p b = 0, y Ay + 2by + 2c = 0.

Thus the set of all touching points is the intersection of the surface ф(х) = 0 and the plane П

П = {x : x\Ap + b) + pTb + 2c = 0}. (6)

As a result one-to-one correspondence between pointp and plane П is established. Consider relation (6) for sphere and circular paraboloid.

Definition 2. Pointp and (d — 1)-dimensional plane П = {x : xTp = 1} are polar with respect to unit sphere.

Definition 3. Pointp and (d — 1)-dimensional plane n = {x : xTp = r2} are polar with respect to sphere with radius r.

Definition 4. Pointp e [Rd +1 and d-dimensional plane

n = {* : -lLPiXi + Pd + 1 + %d + 1 = 0 } (7)

are polar with respect to circular paraboloid

d

xd +1 = 2 XX. (8)

i = 1

Formula (6) was derived assuming that pointp is placed outside quadric, as shown in Fig. 1. In this case plane n intersects the quadric. When pointp is placed inside quadric, then one have to consider all planes passing through p. These planes intersect quadric along certain curves. Tangent planes to quadric at the intersection curve define a cone. With variation of plane, the summit of the resulting cone sweeps precisely the plane polar to p.

Geometrization of the Lagrange transform is formulated in the following theorem due to W. Fenchel.

Theorem 2 (see [18]). Let u(x) : [Rd —[R be convex function with closed epigraph, not equal to and not taking value —to. Then epigraph of function u*(x*) is intersection of halfspaces lying above planes polar with respect to paraboloid (8) to the points of the graph of u.

Let u(x) be smooth strictly convex function. Point x, u(x) on the graph of u has the polar plane {(x*, h) : h = = xTx* — u(x)}. Infinitesimal displacement dx leads to new point x + dx, u(x) + Vu(x)Tdx and new polar plane {(x*, h) : h = xTx* + dxTx* — u(x) — dxTVu(x)}. Intersection of two d-dimensional planes is (d — ^-dimensional plane defined by dxTx* = dxTVu(x). Since differential dx is arbitrary, one obtains

x* = Vu (x). (9)

Thus in full accordance with original formulation of the Lagrange transform, the plane {(x*, h) : h = = xTx* — u(x)} touches the graph of u* at the point x* = Vu(x) and u*(x*) = h (x), where x is expressed via x* from equation (9).

2. DELAUNAY AND VORONOI PARTITIONINGS AND POLAR POLYHEDRA

Consider finite point system % = {pb ...,pn},e R . Let us remind that the Delaunay partitioning is normal partitioning of the Cartesian space into convex polyhedra where each polyhedron is the convex envelope of the points from % lying on the surface of a certain ball, which is empty, i.e. it does not contain any points from % beside vertices of the polyhedron. Dual partitioning to the Delaunay partitioning is called Voronoi partitioning (or Voronoi diagram) and consists of convex polyhedra Vi being the union of the points which are closer to a given pointpi e % compared to any other pointpj e %, i Ф j.

It is well known that the problem of constructing Delaunay and Voronoi partitionings in [R can be reduced to construction of convex envelopes in R . For simplicity consider a finite point set % on the

2

plane R . Consider paraboloid of revolution

1 i 2 2 ^ X3 = 2 (x1 + x2 )

and lift the points from % on the surface of paraboloid, i.e. for a point a e % we define (a ) = ^aT 1 \a\2

The lifted point set is denoted by %l.

Let us consider lower convex envelope of the points from %l which constitutes the graph of the piece-wise linear function x3 = uD(xh x2). Function uD is assigned value +да beyond convex envelope of %. It can be easily shown, that projection of the faces of resulting polyhedral surface on the plane x3 = 0 is nothing else but the Delaunay partitioning. Intersectio

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком