Réunion d'hiver SMC 2009
Université de Windsor, Windsor (Ontario), 5 - 7 décembre 2009

Tendances récentes de la Géométrie discrète
Org: Károly Bezdek (Calgary) et Antoine Deza (McMaster)

KAROLY BEZDEK, University of Calgary, 2500 University Drive N.W., Calgary, AB
On the density of finitely many unit balls relative to their outer parallel domain

We propose to study the following "free" packing problem: Let n > 1 be a positive integer and let r > 0 be a positive real. Then for a given integer d > 1 find the packing of n unit balls in d-dimensional Euclidean space whose density relative to the outer parallel domain of their union having radius r is as large as possible. We give estimates in terms of n, r and d.

TED BISZTRICZKY, University of Calgary
The T(5) property of families of overlapping unit disks

In this joint work with K. Böröczky and A. Heppes, we consider a finite family F of unit disks in the plane with the properties:

  • T(k): any k-element subfamily of F has a (line) transversal, and

  • O(d): the distance between the centres of any two elements of F is greater than d.

It is well known that F has a transversal in each of the following cases:
k = 3 and d > 2Ö2(\sharp)
k = 4 and d > 4/Ö3(\sharp)
k = 5 and d=2 or d > 2.
In this preliminary report, we present arguments that F has a transversal in the case that k = 5 and d = Ö3.

RICHARD CARON, University of Windsor, Windsor, ON, N9B 3P4
Extreme Point Identification and Linear Constraint Classification

The extreme point identification problem is to partition the finite set S = {ai,i Î I} Ì Rn into its subsets N of necessary (extreme) points and N of redundant (non-extreme) points. This problem is important because algorithms to find the convex hull of S are exponential in set cardinality and the convex hull of N is the convex hull of S. Since the necessary points of S are in one-to-one correspondence with the necessary constraints in a representation of the polar dual of S, constraint classification algorithms can be used to determine the partition. We present a hybrid constraint classification algorithm that combines the ability of probabilistic algorithms to quickly detect necessary constraints and the ability of deterministic methods to quickly detect redundant constraints. Numerical experiments establish the effectiveness of this new algorithm.

BOB CONNELLY, Cornell University, Department of Mathematics, Ithaca, NY, USA
Global Rigidity II

Generic global rigidity in the plane is equivalent to vertex 3-connectedness and generic redundant rigidity (the framework remains rigid after the removal of any edge) by result of Berg and Jordan, and Jackson and Jordan; this provides a deterministic polynomial-time algorithm to determine generic global rigidity in the plane. There is a certain class of graphs, generic bar-and-body frameworks, for which there is a deterministic polynomial-time algorithm for generic local rigidity. Our result is that bar-and-body frameworks in d-space are generically globally rigid if and only if they are generically redundantly rigid. Thus generic global rigidity for this class of graphs can be determined by a deterministic polynomial-time algorithm in all dimensions by results of Tay and Tay and Whiteley.

But, unlike the condition for generic local rigidity, it is difficult determine what special configurations to avoid to be sure to have global rigidity. My hope was to find special classes of graphs and configurations that are globally rigid even when perturbed slightly. But there are counterexamples to this attempt in higher dimensions, using the property that a graph is generically globally rigid in d-space if and only if its cone is generically globally rigid in (d+1)-space (a joint result with W. Whiteley mentioned in a previous talk), generic local rigidity is preserved by vertex splitting (a result of W. Whiteley), the necessity of the maximal rank of a stress matrix (due to Gortler, Healy, and Thurston) and a construction due to Jiayang Jiang and Sam Frank.


Let D(d,n) be the maximum possible edge diameter over all polytopes defined by n inequalities in dimension d. The conjecture of Hirsch, formulated in 1957, states that D(d,n) is not greater than n - d. No polynomial bound is known for D(d,n), the best one being quasipolynomial and due to Kalai and Kleitman in 1992. Goodey showed in 1972 that D(4,10) = 5 and D(5,11) = 6. Recently, Bremner and Schewe proved that D(4,11) = D(6,12) = 6. In this follow-up work, we show that D(4,12) = 7 and present evidence that D(5,12) = D(6,13) = 7.

Based on a joint work with David Bremner (University of New Brunswick), William Hua (McMaster University), Lars Schewe (TU Darmstad, Germany).

OLEG MUSIN, University of Texas at Brownsville, 80 Fort Brown, Brownsville, TX 78520
The strong thirteen spheres problem

We solved a long-standing Tammes problem for N=13. The problem asks us to find a configuration of 13 points on the unit sphere in three-space with the maximum angular separation. Using the computer we enumerated all possible jammed (or contact) graphs and found that a known maximal arrangement is unique.

This is joint work with Alexey Tarasov.

DAVID RICHTER, Western Michigan University, Kalamazoo, Michigan, USA
Ghost Symmetries in the Plane

A "ghost symmetry" of a point configuration is a symmetry which appears in some projection of that configuration. Since it is easy to synthesize ghost symmetries by lifting points to higher spaces, ghost symmetries are more interesting when they are abundant. This talk presents a necessary and sufficient condition for the prescribability of a planar configuration to have 3 distinct ghost symmetries. In its statement and proof, the condition appears as an analogue of the classical characterization of 1-skeleta of convex 3-dimensional polytopes due to Steinitz.

ELISSA ROSS, York University, 4700 Keele Street, Toronto, ON M3J 1P3
The Rigidity of Periodic Graphs

Zeolites are a type of molecule with a sieve-like structure where the "holes" of the sieve expand and contract. Using this as motivation, we study the rigidity properties of infinite periodic frameworks. We can think of such a framework in n dimensions as a multigraph embedded on an n-dimensional torus, where the torus may be of fixed or variable dimensions. We use the language of voltage graphs to describe this embedding, and we attempt to characterize the generic infinitesimal rigidity of infinite periodic frameworks by the properties of the underlying voltage graph. This talk presents such a characterization for frameworks on a fixed torus in 2 dimensions, and we outline what is known for graphs on a flexible torus.

CSABA D. TOTH, University of Calgary, 2500 University Dr. NW, Calgary, AB, Canada
Convex partitions with 2-edge connected dual graphs

It is shown that for every set of k disjoint convex polygonal obstacles in the plane with a total of n vertices, there is a partition of the free space around the obstacles into n-k+1 convex cells whose dual graph is 2-edge connected. Every convex cell corresponds to a node in the dual graph, and every vertex of an obstacle corresponds to an edge between two incident convex cells. Questions about the dual graph of a convex partition are motivated by the geometric disjoint compatible matching conjecture.

Joint work with M. Al-Jubeh, M. Hoffmann, M. Ishaque, and D. Souvaine.

ASIA IVIC WEISS, York University, Toronto
Cayley graphs and symmetric 4-polytopes

In any abstract 4-polytope P, the faces of ranks 1 and 2 constitute, in an obvious way, the vertices of a graph which has been called the medial layer graph of P. We consider the Cayley graph for the group generated by a natural set of polarities of a finite, self-dual, regular or chiral 4-polytope P as a covering graph of the medial layer graph of P.

WALTER WHITELEY, York University
Global Rigidity I: Coning

When an embedding of a graph in Euclidean space is congruent to any other embedding with the same edge lengths, we say it is globally rigid. How do you tell? One way is to assume that the configuration is generic, which means that the coordinates of the configuration are algebraically independent over the rationals. There is a matrix, the stress matrix, such that when it has maximal rank, it implies that the graph is generically globally rigid. We will present a summary of some recent results, joint with Bob Connelly, on transferring the generic global rigidity of a graph G between a Euclidean space of dimension d and the cone of the graph in dimension d+1. Key to the new proof is the fact that coning keeps the stress matrix at maximum rank-which is generically, necessary and sufficient for global rigidity of the underlying graph. This result also demonstrates that generic global rigidity of a graph transfers between Euclidean and spherical metrics.

However, geometrically, coning may take a globally rigid framework G(p) to one that is not globally rigid, or take a framework that is not globally rigid to one that is. We briefly indicate a set of examples and counter-examples that arise in basic discussions of global rigidity.

A related preprint is available at:

FENG XIE, McMaster University
On Extensions of Cyclic Arrangements

The average diameter of a bounded cell of a simple arrangement is conjectured to be not greater than the dimension. This conjecture relates to the average case performance of the simplex method of linear programming. Preliminary results indicate that the arrangements maximizing the average diameter are obtained by adding to the cyclic arrangements one hyperplane with the vertices of the cyclic arrangement on the same side of the added hyperplane. The combinatorics of the addition of a pseudo-hyperplane to the cyclic arrangement are well-studied and correspond to higher Bruhat orders. In this talk, we present a computational framework to investigate these special extensions of the cyclic arrangement, and some preliminary results.


l'Université de Windsor    Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences

© Société mathématique du Canada :