A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time

We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon. Our algorithm is considerably simpler than Chazelle's [3] celebrated optimal deterministic algorithm. The new algorithm can be viewed as a combination of Chazelle's algorithm and of simple nonoptimal randomized algorithms due to Clarkson et al. [6], [7], [9] and to Seidel [20]. As in Chazelle's algorithm, it is indispensable to include a bottom-up preprocessing phase, in addition to the actual top-down construction. An essential new idea is the use of random sampling on subchains of the initial polygonal chain, rather than on individual edges as is normally done. Received April 18, 2000, and in revised form December 7, 2000. Online publication June 20, 2001.     

An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set

We describe a deterministic algorithm for computing the diameter of a finite set of points in R ³ , that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog ² n) . The diameter algorithm appears to be the last one in Clarkson and Shor's paper that up to now had no deterministic counterpart with a matching running time. Received May 10, 2000, and in revised form November 3, 2000. Online publication June 22, 2001.     

Numerical Approximation of First Eigenvalues for a Heat Conduction Problem

An eigenvalue problem for a differential operator connected with the heat conduction of a non-steady flow is considered. By using an iterative method for computing the eigenvalues of second kind Fredholm operators (see [1]-[11]) we derive approximation of first eigenvalues closer with respect to results appearing in preceding literature.     

Edgewise Subdivision of a Simplex

In this paper we introduce the abacus model of a simplex and use it to subdivide a d -simplex into k ^d d -simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds. Received June 24, 1999, and in revised form January 13, 2000. Online publication August\/ 11, 2000.     

Strong convergence and certain control conditions for modified Mann iteration

In this paper we propose a new modified Mann iteration for computing fixed points of nonexpansive mappings in a Banach space setting. This new iterative scheme combines the modified Mann iteration introduced by Kim and Xu [T.H. Kim, H.K. Xu, Strong convergence of modified Mann iterations, Nonlinear Anal. 61 (2005) 51–60] and the viscosity approximation method introduced by Moudafi [A. Moudafi, Viscosity approximation methods for fixed-points problems, J. Math. Anal. Appl. 241 (2000) 46–55]. We give certain different control conditions for the modified Mann iteration. Strong convergence in a uniformly smooth Banach space is established.     

Computing a centerpoint of a finite planar set of points in linear time

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set ofn points in the plane, which is optimal compared with theO(n log³ n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.     

Nonlinear versions of a vector maximal principle

Some nonlinear extensions of the vector maximality statement established by Goepfert et al. [A. Goepfert, C. Tammer, C. Z?linescu, On the vectorial Ekeland’s variational principle and minimal points in product spaces, Nonlinear Anal. 39 (2000) 909-922] are given. Basic instruments for these are the Brezis-Browder ordering principle [H. Brezis, F.E. Browder, A general principle on ordered sets in nonlinear functional analysis, Adv. Math. 21 (1976) 355-364] and its logical equivalent in Turinici [M. Turinici, Variational principles on semi-metric structures, Libertas Math. 20 (2000) 161-171].     

Mathematical analysis of a structure-preserving approximation of the bidimensional vorticity equation

Summary. We show the consistency and the convergence of a spectral approximation of the bidimensional vorticity equation, proposed by V. Zeitlin in[13] and studied numerically by I. Szunyogh, B. Kadar, and D. Dévényi in [12], whose main feature is that it preserves the Hamiltonian structure of the vorticity equation. Received February 22, 2000 / Revised version received October 23, 2000 / Published online June 20, 2001     

Differentiation of generalized inverses for rational and polynomial matrices

Our basic motivation is a direct method for computing the gradient of the pseudo-inverse of well-conditioned system with respect to a scalar, proposed in [13] by Layton. In the present paper we combine the Layton’s method together with the representation of the Moore-Penrose inverse of one-variable polynomial matrix from [24] and developed an algorithm for computing the gradient of the Moore-Penrose inverse for one-variable polynomial matrix. Moreover, using the representation of various types of pseudo-inverses from [26], based on the Grevile’s partitioning method, we derive more general algorithms for computing {1}, {1, 3} and {1, 4} inverses of one-variable rational and polynomial matrices. Introduced algorithms are implemented in the programming language MATHEMATICA. Illustrative examples on analytical matrices are presented.     

On a hyperplane section theorem of Gurjar

A hyperplane section theorem by R. V. Gurjar [3] is given a short proof. Power series in any number (at least three) of variables satsifying the condition of the theorem are explicitly constructed. In the course of the proof, the restrictive-looking condition of the theorem is given an easy sufficient condition from the view point of the weighted projective spaces. Received April 12, 2000 / Accepted August 21, 2000 / Published online October 30, 2000     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

On some algorithmic aspects of hypergraphic matroids

Hypergraphic matroids were studied first by Lorea [23] and later by Frank et al. [11]. They can be seen as generalizations of graphic matroids. Here we show that several algorithms developed for the graphic case can be extended to hypergraphic matroids. We treat the following: the separation problem for the associated polytope, testing independence, separation of partition inequalities, computing the rank of a set, computing the strength, computing the arboricity and network reinforcement.     

On a matching statistic

A discrete time process on [0,1] considered in this paper is related to various problems involving two independent samples. In particular one may suggest a simple matching rule for the case of continuously generated samples and a goodness-of-fit test based on the number of unmatched elements. A recurrence formula for computing the exact distribution of this statistic and the asymptotic behavior of its expectation are found.     

Bifurcation Analysis of a Class of Parametrized Two-Point Boundary Value Problems

Summary. In this paper, we study the solution manifold M of a class of nonlinear parametrized two-point boundary value problems. Typical representatives of this class are the shell equations of Bauer, Reiss, Keller [2] and Troger, Steindl [29]. The boundary value problems are formulated as an abstract operator equation T(x,λ)=0 in appropriate Banach spaces. By exploiting the equivariance of T , we obtain detailed information about the structure of M. Moreover, we show how these theoretical results can be used to compute efficiently interesting parts of M with numerical standard techniques. Finally, we present numerical results for the shell equations given in [2] and [29]. Received May 22, 1998; accepted May 23, 2000 Online publication August 8, 2000     

一类生态系统中孤立不变集的指标和联络

对于一类生态模型产生的流,本文通过计算流的孤立不变集的Ｃｏｎｌｅｙ指标来分析它的结构．当流的休止点都是双曲时,进一步讨论了这些休止点间联络的唯一性,这些结果推广了［４］中的相应结束     

On Sets Where Iterates of a Meromorphic Function Zip Towards Infinity

For a transcendental meromorphic function f, various propertiesof the set [formula] were obtained in [8] and [9]. Here we establish analogous propertiesfor the smaller sets [formula] introduced in [5], and [formula] We deduce a symmetry result for Julia sets J(f), and also indicatesome techniques for showing that certain invariant curves liein I'(f), Z(f) and J(f). 2000 Mathematics Subject Classification30D05, 37F10, 37F50.     

The problem of computing the value of a differential game for a positional functional

A dynamical system driven by controls and uncontrollable noise is considered in a game-theoretic setting [1–8]. The problem of feedback control in which the performance index is a positional functional of the motion of the system [8–11] is investigated. On the assumption that the structure of the functional satisfies reasonably general conditions, a procedure is proposed for computing the value of the corresponding differential game. Irrespective of the number of dimensions in the initial problem, as dictated by the structure of the performance index, the proposed procedure reduces to the problem of the successive construction of the upper convex hulls of certain auxiliary functions in domains whose dimension does not exceed that of the phase vector of the system.     

Real Banach ✶ Algebras

In this paper, we study real Banach ✶ algebras systematically. We present the right form of Pták's inequality [1,4] in the real case, and generalize the results of Vukman in [3] to the general case (algebras with or without an identity). Moreover, this paper is a real analogue of Pták's work [1] in the complex case. Received February 22, 2000, Accepted March 14, 2000     

On the density of the set of generators of a polynomial algebra

Let be the polynomial algebra over a field of characteristic . We call a polynomial coordinate (or a generator) if for some polynomials . In this note, we give a simple proof of the following interesting fact: for any polynomial of the form where is a polynomial without constant and linear terms, and for any integer , there is a coordinate polynomial such that the polynomial has no monomials of degree . A similar result is valid for coordinate -tuples of polynomials, for any . This contrasts sharply with the situation in other algebraic systems.

On the other hand, we establish (in the two-variable case) a result related to a different kind of density. Namely, we show that given a non-coordinate two-variable polynomial, any sufficiently small perturbation of its non-zero coefficients gives another non-coordinate polynomial.

     

On Some Generalizations and Refinements of a Ky Fan Inequality

In this paper, a Ky Fan inequality and an inequality by Wu and Wang [10] will be generalized. Some new and improved refinements of the Ky Fan inequality will be put forward.AMS Subject Classification (2000) 26D15