Output-sensitive results on convex hulls,extreme points,and related problems

We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems. We show that thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in time; this is optimal if for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n ^2−γ) time for any constant . Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms the input is assumed to be in general position. This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.     

Largest and smallest maximal sets of pairwise disjoint partitions

Let $\text{X}$ be a maximal set of pairwise disjoint partitions of n into t distinct parts. Let M_t(n) (resp. m_t(n)) denote the size of the largest (resp. smallest) such maximal set $\text{X}$. Upper and lower bounds for $\text{M}{}_{\mathrm{t}}\text{(n)}\text{n}$ and $\text{m}{}_{\mathrm{t}}\text{(n)}\text{n}$ are established.     

On distinct distances among points in general position and other related problems

A set of points in the plane is said to be in general position if no three of them are collinear and no four of them are cocircular. If a point set determines only distinct vectors, it is called parallelogram free. We show that there exist n-element point sets in the plane in general position, and parallelogram free, that determine only O(n ²/√log n) distinct distances. This answers a question of Erd?s, Hickerson and Pach. We then revisit an old problem of Erd?s: given any n points in the plane (or in d dimensions), how many of them can one select so that the distances which are determined are all distinct? — and provide (make explicit) some new bounds in one and two dimensions. Other related distance problems are also discussed.     

On the second smallest distance between finitely many points on the sphere

In the following note we investigate the second smallest distance between finitely many points on the sphere. Actually we look for the smallest upper bound for the second smallest distance between n points on the unit sphere. We solve this problem for n=9 and also we give a general, non-trivial upper bound for the second smallest distance of n points with n9.Supported by the Hungarian National Foundation for Scientific Research, Number 1238.     

Thue type problems for graphs, points, and numbers

A sequence S=s₁s₂…s_n is said to be nonrepetitive if no two adjacent blocks of S are the same. A celebrated 1906 theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set {0,1,2}. This result is the starting point of Combinatorics on Words—a wide area with many deep results, sophisticated methods, important applications and intriguing open problems.The main purpose of this survey is to present a range of new directions relating Thue sequences more closely to Graph Theory, Combinatorial Geometry, and Number Theory. For instance, one may consider graph colorings avoiding repetitions on paths, or colorings of points in the plane avoiding repetitions on straight lines. Besides presenting a variety of new challenges we also recall some older problems of this area.     

Fixed points and quasi-equilibrium problems

A fixed-point theorem for compact acyclic maps defined on convex subsets of notnecessarily locally convex topological vector spaces is applied to the existence of solutions of quasi-equilibrium problems. Such existence theorems extend known ones which were used for unified approaches to quasi-variational inequalities in [1–5] and others.     

Strongly unfoldable,splitting and bounding

Assuming $\mathsf{GCH}$, we show that generalized eventually narrow sequences on a strongly inaccessible cardinal κ are preserved under a one step iteration of the Hechler forcing for adding a dominating κ-real. Moreover, we show that if κ is strongly unfoldable, $2^{\kappa }={\kappa }^{+}$ and λ is a regular cardinal such that , then there is a set generic extension in which .     

Exhausters, optimality conditions and related problems

The notions of exhausters were introduced in (Demyanov, Exhauster of a positively homogeneous function, Optimization 45, 13–29 (1999)). These dual tools (upper and lower exhausters) can be employed to describe optimality conditions and to find directions of steepest ascent and descent for a very wide range of nonsmooth functions. What is also important, exhausters enjoy a very good calculus (in the form of equalities). In the present paper we review the constrained and unconstrained optimality conditions in terms of exhausters, introduce necessary and sufficient conditions for the Lipschitzivity and Quasidifferentiability, and also present some new results on relationships between exhausters and other nonsmooth tools (such as the Clarke, Michel-Penot and Fréchet subdifferentials).     

Largest fixed points of set continuous operators and Boffa's Anti‐Foundation

In Aczel [1], the existence of largest (written “greatest” in Barwise and Moss [2]) fixed points of set continuous operators is proved assuming the schema version of dependent choices in Zermelo‐Fraenkel set theory without the axiom of Foundation. In the present paper, we study whether the existence of largest fixed points of set continuous operators is provable without the schema version of dependent choices, using Boffa's weak antifoundation axioms. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Periodic points of endomorphisms on solenoids and related groups

This paper investigates the problem of finding the possiblesequences of periodic point counts for endomorphisms of solenoids.For an ergodic epimorphism of a solenoid, a closed formula isgiven that expresses the number of points of any given periodin terms of sets of places of finitely many algebraic numberfields and distinguished elements of those fields. The resultextends to more general epimorphisms of compact abelian groups.     

Fixed points,coincidence points and maximal elements with applications to generalized equilibrium problems and minimax theory

In this paper, using a generalization of the Fan–Browder fixed point theorem, we obtain a new fixed point theorem for multivalued maps in generalized convex spaces from which we derive several coincidence theorems and existence theorems for maximal elements. Applications of these results to generalized equilibrium problems and minimax theory will be given in the last sections of the paper.     

On bounding,interior and covering functions

We prove three theorems yielding sufficient conditions for a continuous function f: X → Y to have no isolated bounding points (i.e., points at which it is not an open mapping), to be interior a z (i.e.,f(z) ?f(X)⁰), and to have its image cover a segment. In the first theorem X and Y are rather general topological spaces and some applications to optimal control are discussed. In the second and third theorems X an Y are finite-dimensional and we use the concepts of ordinary and unbounded derivate containers which are a form of set-valued derivatives. The proof of the second theorem also involves the topological degree of f.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

Product-integration with the Clenshaw-Curtis and related points

Summary This paper is concerned with the theoretical properties of a productintegration method for the integral , wherek is absolutely integrable andf is continuous. The integral is approximated by , where the points are given byx _ni =cos(i/n, 0in, and where the weightsw _ni are chosen to make the rule exact iff is any polynomial of degree n. The principal result is that ifkL _p [–1, 1] for somep>1, then the rule converges to the exact result asn for all continuous (or indeed R-integrable) functionsf, and moreover that the sum of the absolute values of the weights converges to the least possible value, namely . A limiting expression for the individual weights is also obtained, under certain assumptions. The results are exteded to other point sets of a similar kind, including the classical Chebyshev points.     

Semimartingales on rays,Walsh diffusions,and related problems of control and stopping

We introduce a class of continuous planar processes, called “semimartingales on rays”, and develop for them a change-of-variable formula involving quite general classes of test functions. Special cases of such processes are diffusions which choose, once at the origin, the rays for their subsequent voyage according to a fixed probability measure in the manner of Walsh (1978). We develop existence and uniqueness results for these “Walsh diffusions”, study their asymptotic behavior, and develop tests for explosions in finite time. We use these results to find an optimal strategy, in a problem of stochastic control with discretionary stopping involving Walsh diffusions.     

Largest signless Laplacian spectral radius of uniform supertrees with diameter and pendent edges (vertices)

Let \mathbb{S}(m; d; k) be the set of k-uniform supertrees with m edges and diameter d; and S₁(m; d; k) be the k-uniform supertree obtained from a loose path u₁; e₁; u₂; e₂,..., u_d; e_d; u_d+1 with length d by attaching m — d edges at vertex u_{\lfloor d/2\rfloor +1}: In this paper, we mainly determine S₁(m; d; k) with the largest signless Laplacian spectral radius in \mathbb{S}(m; d; k) for 3≤d≤m –1: We also determine the supertree with the second largest signless Laplacian spectral radius in \mathbb{S}(m; 3; k): Furthermore, we determine the unique k-uniform supertree with the largest signless Laplacian spectral radius among all k-uniform supertrees with n vertices and pendent edges (vertices).     

Open problems and conjectures,optimal rearrangement problems related to discrete loaded strings

In this section we present some open problems and conjectures about some interesting types of difference equations. Please submit your problems and conjectures with all relevant information to G. Ladas.     

Interval method for bounding level sets: Revisited and tested with global optimization problems

An interval method for bounding level sets, modified to increase its efficiency and to get sharper bounding boxes, is presented. The new algorithm was tested with standard global optimization test problems. The test results show that, while the modified method gives a more valuable, guaranteed reliability result set, it is competitive with non-interval methods in terms of CPU time and number of function evaluations.This work was supported by Grant OTKA 1074/1987, and in part by DAAD Fellowship No. 314/108/004/8 during the author's stay at Düsseldorf University.