On the upper embedding of symmetric configurations with block size 3

We consider the problem of embedding a symmetric configuration with block size 3 in an orientable surface in such a way that the blocks of the configuration form triangular faces and there is only one extra large face. We develop a sufficient condition for such an embedding to exist given any orientation of the configuration, and show that this condition is satisfied for all configurations on up to 19 points. We also show that there exists a configuration on 21 points which is not embeddable in any orientation. As a by-product, we give a revised table of numbers of configurations, correcting the published figure for 19 points. We give a number of open questions about embeddability of configurations on larger numbers of points.     

Tightness in subset bounds for coherent configurations

Association schemes have many applications to the study of designs, codes, and geometries and are well studied. Coherent configurations are a natural generalization of association schemes, however, analogous applications have yet to be fully explored. Recently, Hobart [Mich. Math. J. 58:231–239, 2009] generalized the linear programming bound for association schemes, showing that a subset Y of a coherent configuration determines positive semidefinite matrices, which can be used to constrain certain properties of the subset. The bounds are tight when one of these matrices is singular, and in this paper we show that this gives information on the relations between Y and any other subset. We apply this result to sets of nonincident points and lines in coherent configurations determined by projective planes (where the points of the subset correspond to a maximal arc) and partial geometries.     

Enumeration of graphs with signed points and lines

Our object is to enumerate graphs in which the points or lines or both are assigned positive or negative signs. We also treat several associated problems for which these configurations are self-dual with respect to sign change. We find that the solutions to all of these counting problems can be expressed as special cases of one general formula involving the concatenation of the cycle index of the symmetric group with that of its pair group. This counting technique is based on Pólya's Enumeration Theorem and the Power Group Enumeration Theorem. Using a suitable computer program, we list the number of graphs of each type considered up to twelve points. Sharp asymptotic estimates are also obtained.     

A nonparametric approach to 3D shape analysis from digital camera images — I

This article for the first time develops a nonparametric methodology for the analysis of projective shapes of configurations of landmarks on real 3D objects from their regular camera pictures. A fundamental result in computer vision, emulating the principle of human vision in space, claims that, generically, a finite 3D configuration of points can be retrieved from corresponding configurations in a pair of camera images, up to a projective transformation. Consequently, the projective shape of a 3D configuration can be retrieved from two of its planar views, and a projective shape analysis can be pursued from a sample of images. Projective shapes are here regarded as points on projective shape manifolds. Using large sample and nonparametric bootstrap methodology for extrinsic means on manifolds, one gives confidence regions and tests for the mean projective shape of a 3D configuration from its 2D camera images. Two examples are given: an example of testing for accuracy of a simple manufactured object using mean projective shape analysis, and a face identification example. Both examples are data driven based on landmark registration in digital images.     

Classification and higher order analysis of manipulator singularities

A purely algebraic approach to higher order analysis of (singular) configurations of rigid multibody systems with kinematic loops (CMS) is presented. Rigid body con.gurations are described by elements of the Lie group SE(3) and so the rigid body kinematics is determined by an analytical map f : V → SE(3), where V is the configuration space, an analytic variety. Around regular configurations V has manifold structure but this is lost in singular points. In such points the concept of a tangent vector space does not makes sense but the tangent space C_qV (a cone) to V can still be defined. This tangent cone can be determined algebraically using the special structure of the Lie algebra se (3), the generating algebra of the special Euclidean group SE (3), and the fact that the push forward map f_*, the tangential mapping C_qV → se (3), is given in terms of the mechanisms screw system. Moreover the differentials of f of arbitrary order can be expressed algebraically. The tangent space to the configuration space can be shown to be a hypersurface of maximum degree 4, a vector space for regular points. It is the structure of the tangent cone to V that gives the complete geometric picture of the configuration space around a (singular) point. Identification of the screw system and its matrix representation with the kinematic basic functions of the CMS allows an automatic algebraic analysis of mechanisms.     

Cartan coherent configurations

The Cartan scheme \(\mathcal{X}\) of a finite group G with a (B, N)-pair is defined to be the coherent configuration associated with the action of G on the right cosets of the Cartan subgroup \(B\cap N\) by right multiplication. It is proved that if G is a simple group of Lie type, then asymptotically the coherent configuration \(\mathcal{X}\) is 2-separable, i.e., the array of 2-dimensional intersection numbers determines \(\mathcal{X}\) up to isomorphism. It is also proved that in this case, the base number of \(\mathcal{X}\) equals 2. This enables us to construct a polynomial-time algorithm for recognizing Cartan schemes when the rank of G and the order of the underlying field are sufficiently large. One of the key points in the proof is a new sufficient condition for an arbitrary homogeneous coherent configuration to be 2-separable.     

Low complexity functions and convex sets in \mathbbZk\mathbb{Z}^k

In 1938 Morse and Hedlund proved that a function is periodic if the number of different n-blocks with does not exceed n for some n. In 1940 they studied such functions f with for all positive integers n. These are closely related to Sturmian sequences, which occur in many branches of mathematics, computer science and physics. Recently the authors studied k-dimensional functions with , where is the set of different vectors with for a given configuration . In this paper, we characterize functions satisfying for all configurations . Our proof requires a separation theorem for convex sets of lattice points, which may be of independent interest. Received July 20, 1998     

Apollonian Circle Packings: Geometry and Group Theory II. Super-Apollonian Group and Integral Packings

Apollonian circle packings arise by repeatedly filling the interstices between four mutually tangent circles with further tangent circles. Such packings can be described in terms of the Descartes configurations they contain, where a Descartes configuration is a set of four mutually tangent circles in the Riemann sphere, having disjoint interiors. Part I showed there exists a discrete group, the Apollonian group, acting on a parameter space of (ordered, oriented) Descartes configurations, such that the Descartes configurations in a packing formed an orbit under the action of this group. It is observed there exist infinitely many types of integral Apollonian packings in which all circles had integer curvatures, with the integral structure being related to the integral nature of the Apollonian group. Here we consider the action of a larger discrete group, the super-Apollonian group, also having an integral structure, whose orbits describe the Descartes quadruples of a geometric object we call a super-packing. The circles in a super-packing never cross each other but are nested to an arbitrary depth. Certain Apollonian packings and super-packings are strongly integral in the sense that the curvatures of all circles are integral and the curvature x centers of all circles are integral. We show that (up to scale) there are exactly eight different (geometric) strongly integral super-packings, and that each contains a copy of every integral Apollonian circle packing (also up to scale). We show that the super-Apollonian group has finite volume in the group of all automorphisms of the parameter space of Descartes configurations, which is isomorphic to the Lorentz group O(3, 1).     

Classification of Bivariate Configurations with Simple Lagrange Interpolation Formulae

In 1977 Chung and Yao introduced a geometric characterization in multivariate interpolation in order to identify distributions of points such that the Lagrange functions are products of real polynomials of first degree. We discuss and describe completely all these configurations up to degree 4 in the bivariate case. The number of lines containing more nodes than the degree is used for classifying these configurations.     

The configuration polytope of ℓ-line configurations in Steiner triple systems

It has been shown that the number of occurrences of any ℓ-line configuration in a Steiner triple system can be written as a linear combination of the numbers of full m-line configurations for 1 ≤ m ≤ ℓ; full means that every point has degree at least two. More precisely, the coefficients of the linear combination are ratios of polynomials in v, the order of the Steiner triple system. Moreover, the counts of full configurations, together with v, form a linear basis for all of the configuration counts when ℓ ≤ 7. By relaxing the linear integer equalities to fractional inequalities, a configuration polytope is defined that captures all feasible assignments of counts to the full configurations. An effective procedure for determining this polytope is developed and applied when ℓ = 6. Using this, minimum and maximum counts of each configuration are examined, and consequences for the simultaneous avoidance of sets of configurations explored. To Alex Rosa on the Occasion of his Seventieth Birthday     

The Number of Geometric Bistellar Neighbors of a Triangulation

The theory of secondary and fiber polytopes implies that regular (also called convex or coherent) triangulations of configurations with n points in R ^d have at least n-d-1 geometric bistellar neighbors. Here we prove that, in fact, all triangulations of n points in R ² have at least n-3 geometric bistellar neighbors. In a similar way, we show that for three-dimensional point configurations, in convex position and with no three points collinear, all triangulations have at least n-4 geometric bistellar flips. In contrast, we exhibit three-dimensional point configurations, with a single interior point, having deficiency on the number of geometric bistellar flips. A lifting technique allows us to obtain a triangulation of a simplicial convex 4-polytope with less than n-5 neighbors. We also construct a family of point configurations in R ³ with arbitrarily large flip deficiency. Received November 25, 1996, and in revised form March 10, 1997.     

Linear astral configurations with dihedral symmetry

A linear astral (n_k) configuration is a collection of points and straight lines, so that each point lies on k lines and each line passes through k points, with symmetry (transitivity) classes of points and lines under rotations and reflections mapping the configuration to itself. We discuss the possible structures of astral (n₅) configurations with dihedral symmetry group D_m in the Euclidean plane, and we provide methods to investigate the existence of such configurations. In doing so, we introduce a new class of astral (n₃) configurations.     

The steiner minimal network for convex configurations

SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.     

A generalized Desargues configuration and the pure braid group

In this paper, a configuration with n = (₂^d) points in the plane is described. This configuration, as a matroid, is a Desargues configuration if d = 5, and the union of (₅^d) such configurations if d> 5. As an oriented matroid, it is a rank 3 truncation of the directed complete graph on d vertices. From this fact, it follows from a version of the Lefschetz-Zariski theorem implied by results of Salvetti that the fundamental group π of the complexification of its line arrangement is Artin's pure (or coloured) braid group on d strands.

In this paper we obtain, by using techniques introduced by Salvetti, a new algorithm for finding a presentation of π based on this particular configuration.     

Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction

Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with.

     

Algorithms for the q-model clustering problem with application in switching cabinet manufacturing

The model configuration problem (MCP) is a combinatorial optimization problem with application in the telecommunications manufacturing industry. The product is a switching cabinet, defined by a number of positions (slots) in which specific circuit packs are installed according to the customer requirements (configurations). Variety of customer requirements leads to a relatively large number of distinct configurations. In order to streamline the manufacturing process, a large number of switching cabinets with identical configurations (model cabinets) are produced in advance. A customer order is then filled by selecting a model cabinet whose configuration is relatively close to the customer configuration and performing any necessary circuit pack exchanges to make its configuration identical to the customer requirement. The manufacturing costs are proportional to the number of these circuit pack exchanges, and the q-model configuration problem is to design q different model configurations so as to minimize the total number of exchanges for a given collection of customer orders. We propose three heuristic algorithms for solving the q-model configuration problem and carry out a computational experiment to evaluate their effectiveness.     

The Number of Cyclic Configurations of Type (v3) and the Isomorphism Problem

A configuration of points and lines is cyclic if it has an automorphism that permutes its points in a full cycle. A closed formula is derived for the number of nonisomorphic connected cyclic configurations of type (v₃), i.e. which have v points and lines, and each point/line is incident with exactly three lines/points. In addition, a Bays–Lambossy type theorem is proved for cyclic configurations if the number of points is a product of two primes or a prime power.     

Placement of the Desargues configuration on a cubic curve

Hilbert and Cohn-Vossen once declared that the configurations of Desargues and Pappus are by far the most important projective configurations. These two are very similar in many respects: both are regular and self-dual, both could be constructed with ruler alone and hence exist over the rational plane, the final collinearity in both instances are automatic and both could be regarded as self-inscribed and self-circumscribed p9lygons (see [1, p. 128]). Nevertheless, there is one fundamental difference between these two configurations, viz. while the Pappus-Brianchon configuration can be realized as nine points on a non-singular cubic curve over the complex plane (in doubly infinite ways), it is impossible to get such a representation for the Desargues configuration. In fact, the configuration of Desargues can be placed in a projective plane in such a way that its vertices lie on a cubic curve over a field k if and only if k is of characteristic 2 and has at least 16 elements. Moreover, any cubic curve containing the vertices of this configuration must be singular.This research of all the three authors was supported by the HSERC of Canada.     

A small basis for four-line configurations in steiner triple systems. Dedicated to the memory of gemma holly griggs

Formulae for the numbers of two, three, and four-line configurations in a Steiner triple system of order v, STS(v), are given. While the formulae for two and three-line configurations depend only on v, the same is true for only 5 of the 16 four-line configurations. For the other 11 and fixed v, the number of occurrences of any one of them, in particular the Pasch configuration, determines the number of occurrences of all the others. © 1995 John Wiley & Sons, Inc.     

Some Enumeration Problems on Central Configurations at the Bifurcation Points

In “Counting central configurations at the bifurcation points,” we proposed an algorithm to rigorously count central configurations in some cases that involve one parameter. Here, we improve our algorithm to consider three harder cases: the planar \((3+1)\)-body problem with two equal masses; the planar 4-body problem with two pairs of equal masses which have an axis of symmetry containing one pair of them; the spatial 5-body problem with three equal masses at the vertices of an equilateral triangle and two equal masses on the line passing through the center of the triangle and being perpendicular to the plane containing it.While all three problems have been studied in two parameter cases, numerical observations suggest new results at some points on the bifurcation curves. Applying the improved version of our algorithm, we count at those bifurcation points. As a result, for the \((3+1)\)-body problem, we identify three points on the bifurcation curve where there are 8 central configurations, which adds to the known results of \(8,9,10\) ones. For our 4-body case, at the bifurcation points, there are 3 concave central configurations, which adds to the known results of \(2,4\) ones. For our 5-body case, at the bifurcation point, there is 1 concave central configuration, which adds to the known results of \(0,2\) ones.