On Topological Changes in the Delaunay Triangulation of Moving Points

Let $P$ P be a collection of $n$ n points moving along pseudo-algebraic trajectories in the plane. (So, in particular, there are constants $s,c>0$ s , c > 0 such that any four points are co-circular at most $s$ s times, and any three points are collinear at most $c$ c times.) One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a sub-cubic bound, on the maximum number of discrete changes that the Delaunay triangulation ${\mathrm{DT}}(P)$ DT ( P ) of $P$ P experiences during the motion of the points of $P$ P . In this paper, we obtain an upper bound of $O(n^{2+{\varepsilon }})$ O ( n 2 + ε ) , for any ${\varepsilon }>0$ ε > 0 , under the assumptions that (i) any four points can be co-circular at most twice and (ii) either no triple of points can be collinear more than twice or no ordered triple of points can be collinear more than once.     

A Near-Quadratic Algorithm for Fence Design

A part feeder is a mechanism that receives a stream of identical parts in arbitrary orientations and outputs them oriented the same way. Various sensorless part feeders have been proposed in the literature. The feeder we consider consists of a sequence of fences that extend partway across a conveyor belt; a polygonal part P carried by the belt is reoriented by each fence it encounters. We present an O(m + n² log³n)-time algorithm to compute a sequence of fences that uniquely orients P, if one exists, where m is the total number of vertices and n is the number of stable edges of P. We reduce the problem to searching for a path in a state graph that has O(n³) edges. By exploiting various geometric properties of this graph, we show that it can be represented implicitly and that a desired path can be computed in O(m + n² log³n) time. We believe that our technique is quite general and could be applicable to other part-manipulation problems as well.     

A Shape Optimization Algorithm for Interface Identification Allowing Topological Changes

In this paper, we provide sufficient and necessary conditions for the minimax equality for extended real-valued abstract convex–concave functions. As an application, we get sufficient and necessary conditions for the minimax equality for extended real-valued convex–concave functions.     

A Simple System with Topological Entropy Infinit

Ｌｅｔ（Ｘ，ｄ）ｂｅａｍｅｔｒｉｃｓｐａｃｅ，ａｎｄｆ：Ｘ→Ｘｂｅａｕｎｉｆｏｒｍｌｙｃｏｎｔｉｎｕｏｕｓｍａｐ．Ｗｈｅｎ（Ｘ，ｄ）ｉｓａｃｏｍｐａｃｔｍｅｔｒｉｃｓｐａｃｅ，ｐｅｏｐｌｅｂｅｌｉｅｖｅｔｈａｔｆｈａｓｐｏｓｉｔｉｖｅｔｏｐｏｌｏｇｉ...     

A Topological Intersection Theorem with Applications in H-Spaces

In this paper, a topological intersection theorem of a family of sets with H-convex sections is established. As an application to this theorem, the Nash equilibrium of abstract economy, the Ky-Fan minimax theorem, and an existence problem of solution for quasi-variational inequality are studied. The results presented in this paper modify and extend the corresponding results given in the literature.AMS Subject Classification (2000) 47H10This work is supported by the Foundation of Yunnan Science Technology Commission, China.     

一个具有动态条件的Verigin问题

本文考虑了一个具有动态条件的Verigin问题,得到了这个问题关于时间的局部古典解的存在唯一性.     

A Topological Ivasev-Musatov Theorem

If the sum of a series of positive numbers is not convergentand the series satisfies certain regularity conditions, a probabilitymeasure can be found whose support contains no interval, yetwhose Fourier series decreases faster than the given series.     

A Two-Dimensional Search Used with a Nonlinear Least-Squares Solver

This note describes a modified search strategy for use with a Gauss-Newton method for nonlinear least-squares problems. If a standard line search along the Gauss-Newton vector p is unable to make much progress, a new search direction is constructed which lies in the plane of p and the steepest-descent vector. Numerical experiments show that a quadratic model of the objective function in this plane can yield effective corrections when the basic Gauss-Newton technique experiences difficulty.     

A Topological Minimax Theorem

We present a topological minimax theorem (Theorem 2.2). The topological assumptions on the spaces involved are somewhat weaker than those usually found in the literature. Even when reinterpreted in the convex setting of topological vector spaces, our theorem yields nonnegligible improvements, for example, of the Passy–Prisman theorem and consequently of the Sion theorem, contrary to most results on topological minimax. This work is part of our ongoing effort to elaborate a coherent theory of minimax.     

拓扑空间中的一个非空交定理及其应用

在FC-空间中证明了一新的非空交定理．作为应用，一不动点定理，一极大元定理，一重合点定理和一些极小极大不等式被证明．这些定理推广了近期文献中的结果．     

A Large Subgraph of the Minimum Weight Triangulation

We present an O(n ⁴ )-time and O(n ² )-space algorithm that computes a subgraph of the minimum weight triangulation (MWT) of a general point set. The algorithm works by finding a collection of edges guaranteed to be in any locally minimal triangulation. We call this subgraph the LMT-skeleton. We also give a variant called the modified LMT-skeleton that is both a more complete subgraph of the MWT and is faster to compute requiring only O(n ² ) time and O(n) space in the expected case for uniform distributions. Several experimental implementations of both approaches have shown that for moderate-sized point sets (up to 350 points^1) the skeletons are connected, enabling an efficient completion of the exact MWT. We are thus able to compute the MWT of substantially larger random point sets than have previously been computed. ^1Though in this paper we summarize some empirical findings for input sets of up to 350 points, a variant of the algorithm has been implemented and tested on up to 40,000 points producing connected subgraphs [2]. Received May 29, 1996, and in revised form January 10, 1997.     

拓扑度的一个性质

本建立了拓扑度的一个性质，即拓扑度的容斥性，并提出了一个不动点定理。     

Topological Complexity with Continuous Operations

The topological complexity of algorithms is studied in a general context in the first part and for zero-finding in the second part. In the first part thelevel of discontinuityof a functionfis introduced and it is proved that it is a lower bound for the total number of comparisons plus 1 in any algorithm computingfthat uses only continuous operations and comparisons. This lower bound is proved to be sharp if arbitrary continuous operations are allowed. Then there exists even a balanced optimal computation tree forf. In the second part we use these results in order to determine the topological complexity of zero-finding for continuous functionsfon the unit interval withf(0) ·f(1) < 0. It is proved that roughly log₂log₂?⁻¹comparisons are optimal during a computation in order to approximate a zero up to ?. This is true regardless of whether one allows arbitrary continuous operations or just function evaluations, the arithmetic operations {+, −, *, /}, and the absolute value. It is true also for the subclass of nondecreasing functions. But for the subclass of increasing functions the topological complexity drops to zero even for the smaller class of operations.     

Topological algebras with dense socle

A study is made of topological rings and algebras with dense socle and connections with the theory of annihilator and dual rings. This is followed by an investigation of semisimple Banach algebras which are right complemented and those which are r.w.c.c. with dense socle (i.e., right multiplication is weakly completely continuous).     

A Two-Dimensional Computational Droplet Contact Model

The interaction between capillary fluid films and micro-structural rough surfaces is one of the main challenges in studying self-cleaning mechanisms. The surface behavior of the deformable fluid film is governed by the Young-Laplace equation, which is highly non-linear. Therefore, a numerical solution is introduced using the finite element method, based on a continuum mechanical formulation. Surface and line contact at the fluid-structure interface are modeled by enforcing a contact constraint, and a contact angle, respectively. The numerical solution is validated against the analytical solution of a test case. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Four-Cycled Graphs with Topological Applications

We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards. We introduce a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine the homotopy type of the independence complexes of external extensions of some graphs.     

Geometric Tomography with Topological Guarantees

We consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in $\mathbb R ^3$ from its cross-sections $\mathcal{S }$ with a given set of cutting planes $\mathcal P $ having arbitrary orientations. In this paper, we analyse a very natural reconstruction strategy: a point $x \in \mathbb R ^3$ belongs to the reconstructed object if (at least one of) its nearest point(s) in $\mathcal P $ belongs to $\mathcal{S }$ . We prove that under appropriate sampling conditions, the output of such an algorithm preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that 3-dimensional shape reconstruction from cross-sections comes with theoretical guarantees.