Peculiar loci of ample and spanned line bundles

The bad locus and the rude locus of an ample and base point free linear system on a smooth complex projective variety are introduced and studied. Polarized surfaces of small degree, or whose degree is the square of a prime, with nonempty bad loci are completely classified. Several explicit examples are offered to describe the variety of behaviors of the two loci. Mathematics Subject Classification (2000):14C20, 14J25     

Computing the radius of pointedness of a convex cone

Let Ξ(H) denote the set of all nonzero closed convex cones in a finite dimensional Hilbert space H. Consider this set equipped with the bounded Pompeiu-Hausdorff metric δ. The collection of all pointed cones forms an open set in the metric space (Ξ(H),δ). One possible way of measuring the degree of pointedness of a cone K is by evaluating the distance from K to the set of all nonpointed cones. The number ρ(K) obtained in this way is called the radius of pointedness of the cone K. The evaluation of this number is, in general, a very cumbersome task. In this note, we derive a simple formula for computing ρ(K), and we propose also a method for constructing a nonpointed cone at minimal distance from K. Our results apply to any cone K whose maximal angle does not exceed 120°. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Contractible Edges in 7-Connected Graphs

An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree 7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture. The work partially supported by NNSF of China(Grant number: 10171022)     

On the relative distances of seven points in a plane convex body

Let C be a convex body in the Euclidean plane. The relative distance of points p and q is twice the Euclidean distance of p and q divided by the Euclidean length of a longest chord in C with the direction, say, from p to q. We prove that, among any seven points of a plane convex body, there are two points at relative distance at most one, and one cannot be replaced by a smaller value. We apply our result to determine the diameter of point sets in normed planes. Zsolt Lángi: Partially supported by the Hung. Nat. Sci. Found. (OTKA), grant no. T043556 and T037752 and by the Alberta Ingenuity Fund.     

Intersection formulae for the kernel of a cone

A subset S of Euclidean space is called a cone if it is the union of a set of halflines having the same endpoint called the apex of the cone, and the set of all such apices is denoted by ker _R S and called the R-kernel or, when it does not lead to any confusion with the kernel of a starshaped set, simply the kernel of S. ker _R S is shown to be the intersection of a family of flats passing through some selected boundary points of S. Three independent formulae of this type are established, respectively: for an arbitrary proper subset S, for S closed, and for S closed connected and nonconvex.The author is with the Department of Mathematics, University of Notre Dame, Indiana, on leave from the Mathematical Institute of the Polish Academy of Sciences.     

Approximating Euclidean distances by small degree graphs

Given an undirected edge-weighted graphG=(V,E), a subgraphG′=(V,E′) is at-spanner ofG if, for everyu, v∈V, the weighted distance betweenu andv inG′ is at mostt times the weighted distance betweenu andv inG. We consider the problem of approximating the distances among points of a Euclidean metric space: given a finite setV of points in ℝd, we want to construct a sparset-spanner of the complete weighted graph induced byV. The weight of an edge in these graphs is the Euclidean distance between the endpoints of the edge. We show by a simple greedy argument that, for anyt>1 and anyV ⊂ ℝd, at-spannerG ofV exists such thatG has degree bounded by a function ofd andt. The analysis of our bounded degree spanners improves over previously known upper bounds on the minimum number of edges of Euclideant-spanners, even compared with spanners of boundedaverage degree. Our results answer two open problems, one proposed by Vaidya and the other by Keil and Gutwin. The main result of the paper concerns the case of dimensiond=2. It is fairly easy to see that, for somet (t≥7.6),t-spanners of maximum degree 6 exist for any set of points in the Euclidean plane, but it was not known that degree 5 would suffice. We prove that for some (fixed)t, t-spanners of degree 5 exist for any set of points in the plane. We do not know if 5 is the best possible upper bound on the degree. This research was supported by Conselho Nacional de Desenvolvimento Cientifico e Tecnológico, Proc 203039/87.4 (Brazil).     

Inside S-inner product sets and Euclidean designs

A finite set X in the Euclidean space is called an s-inner product set if the set of the usual inner products of any two distinct points in X has size s. First, we give a special upper bound for the cardinality of an s-inner product set on concentric spheres. The upper bound coincides with the known lower bound for the size of a Euclidean 2s-design. Secondly, we prove the non-existence of 2- or 3-inner product sets on two concentric spheres attaining the upper bound for any d>1. The efficient property needed to prove the upper bound for an s-inner product set gives the new concept, inside s-inner product sets. We characterize the most known tight Euclidean designs as inside s-inner product sets attaining the upper bound.     

On four-colourings of the rational four-space

Summary LetQ ⁴ denote the graph, obtained from the rational points of the 4-space, by connecting two points iff their Euclidean distance is one. It has been known that its chromatic number is 4. We settle a problem of P. Johnson, showing that in every four-colouring of this graph, every colour class is every-where dense.     

Regular polygons in taxicab geometry

A polygon of n sides will be called regular in taxicab geometry if it has n equal angles and n sides of equal taxicab length. This paper will show that there are no regular taxicab triangles and no regular taxicab pentagons. The sets of taxicab rectangles and taxicab squares will be shown to be the same, respectively, as the sets of Euclidean rectangles and Euclidean squares. A method of construction for a regular taxicab 2n-gon for any n will be demonstrated.     

Numerical integration formulas of degree two

Numerical integration formulas in n-dimensional nonsymmetric Euclidean space of degree two, consisting of n+1 equally weighted points, are discussed, for a class of integrals often encountered in statistics. This is an extension of Stroud's theory [A.H. Stroud, Remarks on the disposition of points in numerical integration formulas, Math. Comput. 11 (60) (1957) 257–261; A.H. Stroud, Numerical integration formulas of degree two, Math. Comput. 14 (69) (1960) 21–26]. Explicit formulas are given for integrals with nonsymmetric weights. These appear to be new results and include the Stroud's degree two formula as a special case.     

A correction to the definition of local center

It is known that in order to solve the minimax facility location problem on a graph with a finite set of demand points, only a finite set of possible location points, called ‘local centers’ must be considered.It has been shown that the continuous m-center problem on a graph can be solved by using a series of set covering problems in which each local center covers the demand points at a distance not greater than a corresponding number called ‘the range’ of the local center.However, all points which are at the same distance from more than two demand points, and from which there is no direction where all these distances are decreasing, must also be considered as local centers. This paper proves that, in some special cases, it is not sufficient to consider only the points where this occurs with respect to pairs of demand points. The definition of local center is corrected and the corresponding results and algorithms are revised.     

A NOTE ON CITY BLOCK DISTANCE

In this paper, problem of characterizing the city block distance between two lattice points in k-dimensional Euclidean space is discussed.     

Semi-algebraic Complexity of Quotients and Sign Determination of Remainders

For two nonzero polynomials[formula]the successive signed Euclidean division yields algorithms, that is, semialgebraic computation trees, for tasks such as computing the sequence of successive quotients, deciding the signs of the sequence of remainders in a pointa∈R, deciding the number of remainders, or deciding the degree pattern of the sequence of remainders. In this paper we show lower bounds of ordermlog₂(m) for these tasks, within the computational framework of semi-algebraic computation trees. The inevitably long paths in semi-algebraic computation trees can be specified as those followed by certain prime cones in the real spectrum of a polynomial ring. We give in the paper a positive answer to the question posed in T. Lickteig (J. Pure Appl. Algebra110(2), 131–184 (1996)) whether the degree of the zero-set of the support of a prime cone provides a lower bound on the complexity of isolating the prime cone. The applications are based on the degree inequalities given by Strassen and Schuster and extend their work to the real situation in various directions.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.     

A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres

Summary. The algorithm proved here solves the problem of orthogonal distance regression for the maximum norm with hyperplanes and hyperspheres. For each finite set of points in a Euclidean space of any dimension, the algorithm determines – through finitely many arithmetic operations – all the hyperplanes and hyperspheres that minimize the maximum Euclidean distance measured perpendicularly from the data. The algorithm finds all the slabs (bounded by parallel hyperplanes) and all the spherical shells (bounded by concentric hyperspheres) that contain all the data and are “rigidly supported” by the data (for which there does not exist any other pair of parallel hypersurfaces of the same type that intersect the data at the same points.) The computational complexity of the algorithm increases as the number of data points raised to the dimension of the ambient space. The solutions are then the midrange hyperplanes in the thinnest slabs, and the midrange hyperspheres in the thinnest shells. Their sensitivity to perturbations of the data is of the order of a power of the reciprocal of the smallest angle between two median hyperplanes separating two pairs of data points. The methods of proof consist in showing that if a pair of parallel hyperplanes or hyperspheres is not rigidly supported but encompasses all the data, then there exists a projective shift of their common projective center producing a thinner slab or shell that still contains all the data. Received December 14, 1999 / Revised version received August 30, 2000 / Published online September 19, 2001     

Efficiently navigating a random Delaunay triangulation

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant spanning ratio (w.r.t the Euclidean distance) which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q; cone walk applied to z and q will access at most sites with complexity with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is ‐memoryless with high probability for any pair of start and query point in the domain, for any positive ξ. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 95–136, 2016     

The Euclidean Distance Degree of an Algebraic Variety

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low-rank matrices, the Eckart–Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.     

Iterative factor clustering of binary data

Binary data represent a very special condition where both measures of distance and co-occurrence can be adopted. Euclidean distance-based non-hierarchical methods, like the k-means algorithm, or one of its versions, can be profitably used. When the number of available attributes increases the global clustering performance usually worsens. In such cases, to enhance group separability it is necessary to remove the irrelevant and redundant noisy information from the data. The present approach belongs to the category of attribute transformation strategy, and combines clustering and factorial techniques to identify attribute associations that characterize one or more homogeneous groups of statistical units. Furthermore, it provides graphical representations that facilitate the interpretation of the results.     

An elementary proof of a theorem of Johnson and Lindenstrauss

A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/?²)‐dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± ?). In this note, we prove this theorem using elementary probabilistic techniques. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 60–65, 2002