Dzhuraev’s Formulas and Poly-Bergman Kernels on Domains Möbius Equivalent to a Disk

Let ${U\subset\mathbb{C}}$ be a domain Möbius equivalent to the unit disk. For every non-zero integer j, the poly-Bergman projection B _{U, j} is explicitly represented in terms of the singular integral operator S _{U, j} . If Ω is the complement of a disk, then the action of the Beurling operator S _Ω and its adjoint ${S_\Omega^*}$ on the true poly-Bergman spaces is described. The poly-Bergman kernels of U are explicitly given.     

A dual algorithm for the minimum covering weighted ball problem in {\mathbb{R}^n}

The nonlinear convex programming problem of finding the minimum covering weighted ball of a given finite set of points in ${\mathbb{R}^n}$ is solved by generating a finite sequence of subsets of the points and by finding the minimum covering weighted ball of each subset in the sequence until all points are covered. Each subset has at most n + 1 points and is affinely independent. The radii of the covering weighted balls are strictly increasing. The minimum covering weighted ball of each subset is found by using a directional search along either a ray or a circular arc, starting at the solution to the previous subset. The step size is computed explicitly at each iteration.     

Computing optimal islands

Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n³)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.     

Upper bounds for the height of S-integral points on elliptic curves

We establish new upper bounds for the height of the S-integral points of an elliptic curve. This bound is explicitly given in terms of the set S of places of the number field K involved, but also in terms of the degree of K, as well as the rank, the regulator and the height of a basis of the Mordell–Weil group of the curve. The proof uses the elliptic analogue of Baker’s method, based on lower bounds for linear forms in elliptic logarithms.     

Projection-forcing multisets of weight changes

Let F be a finite field. A multiset S of integers is projection-forcing if for every linear function ?:Fn→Fm whose multiset of weight changes is S, ? is a coordinate projection up to permutation and scaling of entries. The MacWilliams Extension Theorem from coding theory says that S={0,0,…,0} is projection-forcing. We give a (super-polynomial) algorithm to determine whether or not a given S is projection-forcing. We also give a condition that can be checked in polynomial time that implies that S is projection-forcing. This result is a generalization of the MacWilliams Extension Theorem and work by the first author.     

On support points for some families of univalent functions

Given a closed subset of the familyS* (α) of functions starlike of order α, a continuous Fréchet differentiable functional,J, is constructed with this collection as the solution set to the extremal problem ReJ(f) overS* (α). The support points ofS* (α) is completely characterized and shown to coincide with the extreme points of its convex hulls. Given any finite collection of support points ofS* (α), a continuous linear functional,J, is constructed with this collection as the solution set to the extremal problem ReJ(f) overS* (α).     

Noisy colored point set matching

We propose a process for determining approximated matches, in terms of the bottleneck distance, under color preserving rigid motions, between two colored point sets A,B∈R², |A|≤|B|. We solve the matching problem by generating all representative motions that bring A close to a subset B^′ of set B and then using a graph matching algorithm. We also present an approximate matching algorithm with improved computational time. In order to get better running times for both algorithms we present a lossless filtering preprocessing step. By using it, we determine some candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B^′ of S. Then, we solve the matching problem between A and every candidate zone. Experimental results using both synthetic and real data are reported to prove the effectiveness of the proposed approach.     

Improved Results on Geometric Hitting Set Problems

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ?³ and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only.     

On spherically convex sets and Q-matrices

Let K be a closed spherically convex subset of S^n?1 that is contained in a hemisphere, and x?(K) the radial projection onto S^n?1 of the centroid of K. Then p^Tx?(K)>0 for all p ? K. A specialization of this result to spherical simplices is used to derive a necessary condition for Q-matrices, i.e., matrices for which every corresponding linear complementarity problem has at least one solution.     

Hilbert subsets ands-integral points

A classical tool for studying Hilbert's irreducibility theorem is Siegel's finiteness theorem forS-integral points on algebraic curves. We present a different approach based ons-integral points rather thanS-integral points. Given an integers>0, an elementt of a fieldK is said to bes-integral if the set of placesv ∈M _K for which |t|_v > l is of cardinality ≤s (instead of contained inS for “S-integral”). We prove a general diophantine result fors-integral points (Th.1.4). This result, unlike Siegel's theorem, is effective and is valid more generally for fields with the product formula. The main application to Hilbert's irreducibility theorem is a general criterion for a given Hilbert subset to contain values of given rational functions (Th.2.1). This criterion gives rise to very concrete applications: several examples are given (§2.5). Taking advantage of the effectiveness of our method, we can also produce elements of a given Hilbert subset of a number field with explicitely bounded height (Cor.3.7). Other applications, including the case thatK is of characteristicp>0, will be given in forthcoming papers ([8], [9]).     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

Variable selection in model-based clustering using multilocus genotype data

We propose a variable selection procedure in model-based clustering using multilocus genotype data. Indeed, it may happen that some loci are not relevant for clustering into statistically different populations. Inferring the number K of clusters and the relevant clustering subset S of loci is seen as a model selection problem. The competing models are compared using penalized maximum likelihood criteria. Under weak assumptions on the penalty function, we prove the consistency of the resulting estimator ${(\widehat{K}_n, \widehat{S}_n)}$ . An associated algorithm named Mixture Model for Genotype Data (MixMoGenD) has been implemented using c++ programming language and is available on http://www.math.u-psud.fr/~toussile. To avoid an exhaustive search of the optimum model, we propose a modified Backward-Stepwise algorithm, which enables a better search of the optimum model among all possible cardinalities of S. We present numerical experiments on simulated and real datasets that highlight the interest of our loci selection procedure.     

Characterizations of n-connected and n-line connected graphs

The following two theorems are proved: (1) A graph G with at least n + 1 points, n ≥ 2, is n-connected if and only if for each set S of n distinct points of G and for each two point subset T of S there is a cycle of G that contains the points of T and avoids the points of S ? T. (2) A graph G with at least n + 1 lines, n ≥ 2, with no isolated points is n-line connected if and only if for each set S of n distinct lines of G and for each two line subset T of S there is a circuit of G that contains the lines of T and avoids the lines of S ? T.     

The Connectivity of addition Cayley graphs

For any finite abelian group G and any subset S ⊆ G, we determine the connectivity of the addition Cayley graph induced by S on G. Moreover, we show that if this graph is not complete, then it possesses a minimum vertex cut of a special, explicitly described form.     

On the complexity of a family of generalized matching problems

We consider a family of generalized matching problems called k-feasible matching (k-RM) problems, where k? {1,2,3,…} ∪ {∞}. We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of {1,2,…} ∪ {∞}, there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

On the maximum empty rectangle problem

Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n²) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)²) expected time.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

The problem of recovering the permittivity coefficient from the modulus of the scattered electromagnetic field

Under consideration is the stationary system of equations of electrodynamics relating to a nonmagnetic nonconducting medium. We study the problem of recovering the permittivity coefficient ε from given vectors of electric or magnetic intensities of the electromagnetic field. It is assumed that the field is generated by a point impulsive dipole located at some point y. It is also assumed that the permittivity differs from a given constant ε₀ only inside some compact domain Ω ? R³ with smooth boundary S. To recover ε inside Ω, we use the information on a solution to the corresponding direct problem for the system of equations of electrodynamics on the whole boundary of Ω for all frequencies from some fixed frequency ω ₀ on and for all y ∈ S. The asymptotics of a solution to the direct problem for large frequencies is studied and it is demonstrated that this information allows us to reduce the initial problem to the well-known inverse kinematic problem of recovering the refraction index inside Ω with given travel times of electromagnetic waves between two arbitrary points on the boundary of Ω. This allows us to state uniqueness theorem for solutions to the problem in question and opens up a way of its constructive solution.