The vanishing ideal of a finite set of closed points in affine space

Given a finite set of closed rational points of affine space over a field, we give a Gröbner basis for the lexicographic ordering of the ideal of polynomials which vanish at all given points. Our method is an alternative to the Buchberger-Möller algorithm, but in contrast to that, we determine the set of leading terms of the ideal without solving any linear equation but by induction over the dimension of affine space. The elements of the Gröbner basis are also computed by induction over the dimension, using one-dimensional interpolation of coefficients of certain polynomials.     

The timelike cut locus and conjugate points in Lorentz 2-step nilpotent Lie groups

We investigate the timelike cut locus and the locus of conjugate points in Lorentz 2-step nilpotent Lie groups. For these groups with a timelike center, we give some criteria for the existence of conjugate points along timelike geodesics. We show for instance that a nonsingular timelike geodesic which is translated by an element of the group has a conjugate point. For those that we will call of GH-type, and for those which are globally hyperbolic with a timelike center and a one-dimensional derived subgroup, we show that if in addition the derived subgroup is spacelike, then nonsingular timelike geodesics maximize distance up to and including the first conjugate point. Other related results and corollaries are also obtained.Mathematics Subject Classification (2000): 53C50, 53C22, 22E25     

Vesicle computers: Approximating a Voronoi diagram using Voronoi automata

Irregular arrangements of vesicles filled with excitable and precipitating chemical systems are imitated by Voronoi automata - finite-state machines defined on a planar Voronoi diagram. Every Voronoi cell takes four states: resting, excited, refractory and precipitate. A resting cell excites if it has at least one neighbour in an excited state. The cell precipitates if the ratio of excited cells in its neighbourhood versus the number of neighbours exceeds a certain threshold. To approximate a Voronoi diagram on Voronoi automata we project a planar set onto the automaton lattice, thus cells corresponding to data-points are excited. Excitation waves propagate across the Voronoi automaton, interact with each other and form precipitate at the points of interaction. The configuration of the precipitate represents the edges of an approximated Voronoi diagram. We discover the relationship between the quality of the Voronoi diagram approximation and the precipitation threshold, and demonstrate the feasibility of our model in approximating Voronoi diagrams of arbitrary-shaped objects and in constructing a skeleton of a planar shape.     

Minimum-Area ellipse containing a finite set of points. II

We continue the investigation of the problem of construction of a minimum-area ellipse for a given convex polygon (this problem is solved for a rectangle and a trapezoid). For an arbitrary polygon, we prove that, in the case where the boundary of the minimum-area ellipse has exactly four or five common points with the polygon, this ellipse is the minimum-area ellipse for the quadrangles and pentagons formed by these common points. Translated from Ukrainskii Matematicheskii Zhurnal, Vol.50, No.8, pp. 1098–1105, August, 1998.     

Minimum-Area ellipse containing a finite set of points. I

From the geometric point of view, we consider the problem of construction of a minimum-area ellipse containing a given convex polygon. For an arbitrary triangle, we obtain an equation for the boundary of the minimum-area ellipse in explicit form. For a quadrangle, the problem of construction of a minimumarea ellipse is connected with the solution of a cubic equation. For an arbitrary polygon, we prove that if the boundary of the minimum-area ellipse has exactly three common points with the polygon, then this ellipse is the minimum-area ellipse for the triangle obtained. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 7, pp. 980–988, July, 1998.     

The embracing Voronoi diagram and closest embracing number

A point q is embraced by a set of points S if q is interior to the convex hull of S [8]. In some illumination applications where points of S are lights and q is a point to be illuminated, the embracing concept is related to a good illumination [4, 6], also known as the ∆-guarding [12] and the well-covering [10]. In this paper, we are not only interested in convex dependency (which is actually the embracing notion) but also in proximity. Suppose that the sites of S are lights or antennas with limited range; due to their limited power, they cover a disk of a given radius r centered at the sites of S. Only the points lying in such disks are illuminated. If we want to embrace the point q with the minimum range r, we need to know which is the closest light s _q to q such that q lies in the convex hull formed by s _q and the lights of S closer to q than s _q . This subset of S related to point q is called the closest embracing set for q in relation to S and its cardinality is the closest embracing number of q. By assigning every point q in the convex hull of S to its closest embracing site s _q , we obtain a partition of the convex hull that we call the embracing Voronoi diagram of S. This paper proves some properties of the embracing Voronoi diagrams and describes algorithms to compute such diagrams, as well as the levels in which the convex hull is decomposed regarding the closest embracing number.     

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.     

Learning a function from noisy samples at a finite sparse set of points

In learning theory the goal is to reconstruct a function defined on some (typically high dimensional) domain Ω, when only noisy values of this function at a sparse, discrete subset ω⊂Ω are available.In this work we use Koksma–Hlawka type estimates to obtain deterministic bounds on the so-called generalization error. The resulting estimates show that the generalization error tends to zero when the noise in the measurements tends to zero and the number of sampling points tends to infinity sufficiently fast.     

Calculation of the discrepancy of a finite set of points in the unit n-cube

An algorithm for calculating the discrepancy of finitely many points in the unit n-cube [0, 1]ⁿ is suggested. This algorithm is easy to program. For 2 ≤ n ≤ 4, the suggested algorithm is significantly faster than Bundschuh and Zhu’s algorithm. For larger n, whether this algorithm is faster depends on the number of points.     

A geometric inequality for a finite set of points on a sphere and its applications

In this paper we present a geometric inequality for a finite number of points on an (n–1)-dimensional sphere S _n–1(R). As an application, we obtain a geometric inequality for finitely many points in the n-dimensional Euclidean space E ⁿ.     

On extremums of sums of powered distances to a finite set of points

In this paper we investigate the extremal properties of the sum $$\begin{array}{ll} \sum\limits_{i=1}^n|MA_i|^{\lambda}, \end{array}$$ where A _i are vertices of a regular simplex, a cross-polytope (orthoplex) or a cube and M varies on a sphere concentric to the sphere circumscribed around one of the given polytopes. We give full characterization for which points on Γ the extremal values of the sum are obtained in terms of λ. In the case of the regular dodecahedron and icosahedron in ${\mathbb{R}^3}$ we obtain results for which values of λ the corresponding sum is independent of the position of M on Γ. We use elementary analytic and purely geometric methods.     

On the complexity of some Euclidean problems of partitioning a finite set of points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).