Variational principles for circle patterns and Koebe's theorem

We prove existence and uniqueness results for patterns of circles with prescribed intersection angles on constant curvature surfaces. Our method is based on two new functionals--one for the Euclidean and one for the hyperbolic case. We show how Colin de Verdière's, Brägger's and Rivin's functionals can be derived from ours.

     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

On polygons circumscribing a closed convex curve

Length and area formulas for closed polygonal curves are derived, as functions of the vertex angles and the distances to the lines containing the sides. Applications of the formulas are made to the class of polygons which circumscribe a given convex curve and have a prescribed sequence of vertex angles. Geometric conditions are given for polygons in the class which have extremal perimeter or area.     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

REMARKS ON THE ZIG-ZAG THEOREM

The classical Zig-zag Theorem [1] says that if an equilateral closed 2m-gon shuttles between two given circles of the Euclidean 3-space, then the vertices of the polygon can be moved smoothly along the circles without changing the lengths of the sides of the polygon. First we prove that the Zig-zag Theorem holds also in the hyperbolic, Euclidean and spherical n-spaces, and in fact the circles can be replaced by straight lines or any kind of cycles. In the second part of the paper we restrict our attention to planar zig-zag configurations. With the help of an alternative formulation of the Zig-zag Theorem, we establish two duality theorems for periodic zig-zags between two circles. This revised version was published online in August 2006 with corrections to the Cover Date.     

Motion by curvature of planar curves with end points moving freely on a line

This paper deals with the motion by curvature of planar curves having end points moving freely along a line with fixed contact angles to this line. We first prove the existence and uniqueness of self-similar shrinking solution. Then we show that the curve shrinks to a point in a self-similar manner, if initially the curve is a graph.     

Lower bounds for computing geometric spanners and approximate shortest paths

We consider the problems of constructing geometric spanners, possibly containing Steiner points, for a set of n input points in d-dimensional space , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles on the plane. The complexities of these problems are shown to be Ω(n log n) in the algebraic computation tree model. Since O(n log n)-time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

多边形螺环链关于Hosoya指标的极值问题

Hosoya指标是化学图论研究中较为流行和重要的拓扑指标之一.首先,根据线性的、无分支的、饱和的多螺环化合物的简单分子结构图定义了"多边形螺环链";其次,研究了多边形螺环链关于Hosoya指标的极值问题;同时,得到了多边形螺环链关于Hosoya指标的排序.     

Generic Banach spaces and generic simplexes

We give a systematic study of certain class of generic Banach spaces. We show that they distinguish between an array of different properties related to smoothness of equivalent norms such as for example the Mazur intersection property or the existence of convex sets supported by all of their points. We also examine the dual constructions of generic Choquet simplexes with extra requirements such as for example those of Poulsen and Bauer asking that the set of extremal points is dense or closed, respectively.     

Positive eigenvalues for nonlinear multivalued noncompact operators with applications to differential operators

The first part of Section 1 contains two theorems concerning the existence of positive eigenvalues and corresponding eigenvectors for multivalued and not necessarily compact mappings. Theorem 1 contains as special cases the Birkhoff-Kellogg and Krasnoselskii theorems for single-valued compact mappings while Theorem 2 includes a single-valued result of Reich and some results of Schaefer concerning the existence of positive eigenvalues. The second part of Section 1 contains Theorem 3, which extends another result of Schaefer for positive compact mappings to positive eigenvalue problems involving not necessarily compact mappings. In Section 2 our Theorem 1 is applied to positive eigenvalue problems involving quasilinear ordinary integro-differential operators, quasilinear elliptic operators, and nonlinear ordinary differential operators.     

The isodiametric problem with lattice-point constraints

In this paper, the isodiametric problem for centrally symmetric convex bodies in the Euclidean d-space \Bbb R^d{\Bbb R}^d containing no interior non-zero point of a lattice L is studied. It is shown that the intersection of a suitable ball with the Dirichlet-Voronoi cell of 2L is extremal, i.e., it has minimum diameter among all bodies with the same volume. It is conjectured that these sets are the only extremal bodies, which is proved for all three dimensional and several prominent lattices.     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

On the minimal length of extremal rays for Fano four-folds

The minimum of intersection numbers of the anti-canonical divisor with rational curves on a Fano manifold is called pseudo-index. It is expected that the intersection number of anti-canonical divisor attains to the minimum on an extremal ray, i.e. there exists an extremal rational curve whose intersection number with the anti-canonical divisor equals the pseudo-index. In this note, we prove this for smooth Fano four-folds having birational contractions.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.     

The nonsymmetric case of the Keller-Segel model in chemotaxis: some recent results

Looking at the nonsymmetric case of a reaction-diffusion model known as the Keller-Segel model, we summarize known facts concerning (global in time) existence and prove new blowup results for solutions of this system of two strongly coupled parabolic partial differential equations. We show in Section 4, Theorem 4, that if the solution blows up under a condition on the initial data, blowup takes place at the boundary of a smooth domain . Using variational techniques we prove in Section 5 the existence of nontrivial stationary solutions in a special case of the system. Received April 2000     

Constructions of Solutions to Generalized Sylvester and Fermat–Torricelli Problems for Euclidean Balls

The classical problem of Apollonius is to construct circles that are tangent to three given circles in the plane. This problem was posed by Apollonius of Perga in his work “Tangencies.” The Sylvester problem, which was introduced by the English mathematician J.J. Sylvester, asks for the smallest circle that encloses a finite collection of points in the plane. In this paper, we study the following generalized version of the Sylvester problem and its connection to the problem of Apollonius: given two finite collections of Euclidean balls, find the smallest Euclidean ball that encloses all the balls in the first collection and intersects all the balls in the second collection. We also study a generalized version of the Fermat–Torricelli problem stated as follows: given two finite collections of Euclidean balls, find a point that minimizes the sum of the farthest distances to the balls in the first collection and shortest distances to the balls in the second collection.     

關閉撓曲線的全曲率

<正> §1.引言.大家知道,微分幾何學所討論的一般是關於圖形的局部性質.但是這些局部性質與圖形的整個性質間常存在有某些關係.討論圖形的整個性質的微分幾何學叫做整體性的.關於整體性微分幾何學有這樣的一個著名定理:設一關閉撓曲線C     

On the Existence of Positive Solutions ofSingular Second Order BoundaryValue Problems

This paper deals with the existence of positive solutions of the equation u“ f(t,u)=0 with linear boundary conditions. We show the existence of at least onepositive solution if f is neither superlinear nor sublinear on u by a simple application of afixed point Theorem in cones.     

On a cubic variational problem

An extremal curve of the simplest variational problem is a continuously differentiable function. Hilbert’s differentiability theorem provides a sufficient condition for the existence of the second derivative of an extremal curve. It is desirable to have a simple example in which the condition of Hilbert’s theorem is violated and an extremal curve is not twice differentiable.In this paper, a cubic variational problem with the following properties is analyzed. The functional of the problem is bounded neither above nor below. There exists an extremal curve for this problem which is obtained by sewing together two different extremal curves and not twice differentiable at the sewing point. Despite this unfavorable situation, an attempt to apply the method of steepest descent (in the form proposed by V.F. Dem’yanov) to this problem is made. It turns out that the method converges to a stationary curve provided that a suitable step size rule is chosen.