|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Planar Manhattan Local Minimal And Critical Networksстатья
- Авторы: Ivanov A.O., Hong Van Le, Tuzhilin A.A.
- Журнал: Educational Internet-Journal "Computer Graphics & Geometry
- Том: 1
- Номер: 1
- Год издания: 1999
- Первая страница: 25
- Последняя страница: 49
- Аннотация: In the present paper we consider one-dimensional branching extremals of Lagrangian type functionals. Such extremals appeared first as solutions of the classical Steiner problem asking to find the shortest network, i.e., a connected system of paths of the least length, among all networks spanning a given finite set of terminal points in the plane. The Steiner Problem has a long history and attracts the attention of many well-known mathematicians as from P. Fermat and C. Gauss. Among the reasons of this unabating interest is a lot of important applications of the Steiner problem such as Transportation problem. In the case of the Steiner problem the corresponding Lagrangian is the length of the velocity vector of an edge of a network in consideration and the obtained functional is called the length functional. It is well known that a network is an extremal of the length functional if and only if it is local minimal, i.e., each sufficiently small part of such a network is a solution of the Steiner Problem with respect to the appropriate terminal set. However, this fact have no place for general functionals. In the present paper we investigate the functional of Manhattan length whose lagrangian equals the sum of absolute values of projections of velociy vector onto coordinate axis. Such functionals are useful for solving problems appearing in Electronics, Robotics, chip design, etc. It turns out that for such functional the local minimality does not imply the extremality (however, each extreme network is local minimal). In the case of Manhattan plane we present a ctriterion of extremality of a local minimal network. This criterion demonstrates that the extremality with respect to Manhattan length functional is a global topological property of networks.
- Добавил в систему: Тужилин Алексей Августинович