---

Géométrie discrète et convexe
Org: Karoly Bezdek (Calgary) et Jozsef Solymosi (UBC)
[PDF]

---

KAROLY BEZDEK, University of Calgary, 2500 University Drive N.W., Calgary, AB T2N 1N4
On the illumination parameters of smooth convex bodies [PDF]

Let K be an o-symmetric convex body in d-dimensional Euclidean space and let |x| denote the norm of any point (vector) in d-space with respect to the norm generated by the centrally symmetric convex body K. Then let a(K) denote the minumum of the sum of the norms of points whose convex hull contains K. (Note that a(K) coincides with the illumination parameter of smooth convex bodies introduced by K. Bezdek in 1991.) In the talk we present lower and upper bounds on a(K).

This is a joint work with A. Litvak (Univ. of Alberta).

TED BISZTRICZKY, University of Calgary
Transversals and Convex Sets [PDF]

With Helly's Theorem as the starting point, Transversal Theory has been one of the areas of constant research during the past fifty years in Discrete and Combinatorial Geometry. The central problem is to determine conditions under which there is a line (the transversal) that intersect every member of a family of compact convex sets in the Euclidean plane. We present a very brief history of the subject, concluding with recent developments of the past year.

AIDEN BRUEN, University of Calgary,Mathematics and Statistics
Co-tangency sets and a configuration theorem [PDF]

In the projective plane W over a field F let S be a set of points. Assume also that there is a 1-1 [injective] mapping f from S into the lines of W satisfying the following two properties.

A. For P in S,f(P) does not contain P.
B. If P, Q are distinct points of S, then the points P, Q and R [which is the intersection of f(P) with f(Q)] are collinear. Then S is called a CO-TANGENCY set in W.

In this lecture we present a structural result for co-tangency sets. Following this we present some applications including a classical result due initially to M. O. Nan.

BOB ERDAHL, Queen's University
Reducible and irreducible Voronoi polytopes for lattices [PDF]

There is an interesting question as to whether a Voronoi polytope can be written as the Minkowski sum of Voronoi polytopes in complementary subspaces. It is convenient to say that a Voronoi polytope is reducible if it can be written as such a Minkowski sum, but irreducible otherwise. This situation can be characterized in terms of the Venkov Graph, which will be defined in the course of the talk-the Voronoi polytope is irreducible if and only if the corresponding Venkov Graph is connected.

I will describe how the question of reducibility relates to the theory of metrical forms for lattices, the question of the number of distinct tilings that can be constructed from a given Voronoi polytope, and the Scaling Theorem of Matroid Theory.

THOMAS HALES, Pittsburgh, USA

ALEX IOSEVICH, University of Missouri
Erdos distance problem in vector spaces over finite fields [PDF]

The classical Erdos distance problem says that N points in R^d determine at least N^[ 2/(d)]-d Euclidean distances. We shall discuss an analog of this problem in vector spaces over finite fields. Estimates for classical Kloosterman sums play an important role.

DAVID KIRKPATRICK, University of British Columbia, Vancouver, BC
On the existence and construction of bounded curvature paths in narrow roadways [PDF]

General experience shows that narrower roadways are harder to traverse for vehicles with a bounded turning radius. One way to quantify this is to establish a sharp width threshold t such that

(i) every roadway of width at least t (independent of its layout) is guaranteed to have a unit curvature-bounded traversal, and
(ii) for any width w < t there exist roadways of width w that admit no such traversal.

I will discuss the threshold t, extremal roadways, and related questions: if a given roadway has width less than t, how hard is it to determine its traversibility; if a traversal exists, how hard is it to construct? Applications to cutting logs (as opposed to log-factors) will also be mentioned.

IZABELLA LABA, University of British Columbia, Vancouver, BC
An incidence theorem for pseudoflats [PDF]

We prove a Pach-Sharir type incidence theorem for a class of algebraic curves in Rⁿ and algebraic surfaces in R³.

Joint work with Jozsef Solymosi.

ZSOLT LANGI, University of Calgary, 2500 University Dr. NW, Calgary, AB T2N 1V4
Ball-polytopes and 1-convexity [PDF]

For points p,q Î Rⁿ, [p,q]₁ denotes the intersection of all the unit balls that contain p and q. A set of diameter at most two is called 1-convex if, for any pair p,q of its points, it contains [p,q]₁. The intersection of finitely many unit balls is called a ball-polytope. In this talk we examine which properties of convex sets and convex polytopes can be translated to the language of 1-convex sets and ball-polytopes.

This is joint work with K. Bezdek, M. Naszodi and P. Papez.

MARTON NASZODI, University of Calgary, 2500 University Dr. NW, Calgary, Alberta T2N 1N4
Touching Homothetic Bodies and Antipodality [PDF]

An antipodal set in Euclidean n-space is a set of points with the property that through any two of them there is a pair of parallel hyperplanes supporting the set. In this talk, I will present two research topics that are connected by the idea of antipodality.

The first part of the talk will focus on the extension of the above concept to hyperbolic n-space. This is joint work with Károly Bezdek and Deborah Oliveros.

In the second part, the maximum number of touching positive homothetic copies of a convex body in Euclidean n-space will be discussed. According to a conjecture of Károly Bezdek and János Pach, this number should be 2ⁿ; which bound, if it holds, is sharp as it is attained by cubes. The previously known bound was 3ⁿ which I improved to 2⁽ⁿ⁺¹⁾.

SUBHASH SURI, University of California, Santa Barbara, USA
Detecting Cuts in Sensor Networks [PDF]

We investigate a geometric problem motivated by sensor networks, which have emerged as a model for ubiquitous computing and monitoring of the physical world. If sensor networks are to act as our remote "eyes and ears", then we need to ensure that any significant failure (natural or adversarial) suffered by the network is promptly and efficiently detected.

In this talk we will consider a concrete problem of detecting linear cuts that isolate at least e fraction of the nodes from the base station. We show that the base station can detect whenever an e-cut occurs by monitoring the status of just O(1/e) nodes in the network. Our scheme is deterministic and it is free of false positives: no reported cut has size smaller than en/2. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1/e) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on sampling.

This is joint work with Nisheeth Shrivastava and Csaba Toth.

GABOR TARDOS, Simon Fraser University / Renyi Institute, Budapest
Extremal theory of geometric graphs [PDF]

In this survey talk we consider how many edges a geometric graph with n vertices may have if it does not contain some specific forbidden configuration as a subgraph. Here a geometric graph is a graph whose vertices are points in general position in the plane and whose edges are straight line segments.

The simplest forbidden configuration to consider is a pair of crossing edges: if no pair of edges crosses, we have a planar graph with at most 3n-6 edges. Agarwal et al. considered three pairwise crossing edges and proved the number of edges is still linear if this forbidden configuration is not contained. Recently Eyal Ackerman extended the same result to four pairwise crossing edges. With Ackerman we found the maximal number of edges in a geometric graph not containing three pairwise crossing edges within a small additive constant. It is a challenge to extend the linear bound to the forbidden configuration of five (or more) pairwise crossing edges. At present Valtr's O(nlogn) bound is the best.

Another natural choice for a forbidden configuration is the self-crossing drawings of a small (planar) graph. With Pach, Pinchasi, and Tóth we proved that the maximal number of edges in a geometric graph not containing a self-crossing path of three edges is Q(nlogn). For longer self-crossing paths as forbidden patterns the exact order of magnitude is not known, but it is larger than linear (as shown by a randomized pruning procedure) and is o(nlogn). For forbidden self-intersecting cycles of length 4 we proved an O(n^3/2logn) bound on the number of edges with Adam Marcus, which is almost tight as abstract graphs with W(n^3/2) edges and no C₄ subgraphs exist. This result found many applications in other parts of combinatorial geometry.

Finding the maximal number of edges for other types of forbidden patterns (and tighter estimates for some of the above patterns) raises many interesting research problems.

NICOLE TOMCZAK-JAEGERMANN, Alberta

CSABA TOTH, MIT, Cambridge, MA 02139, USA
The number of minimum volume tetrahedra [PDF]

Determining the maximum number of unit distances determined by n points in the plane is one of the notoriously hard Erdös problems in combinatorial geometry. It is easy to give a tight bound on number of occurrences of the minimum and maximum distance, which is at most 3n-O(Ön) and n, respectively. Finding the maximum number of unit area triangles determined by n points in the plane is similarly hard as the unit distance problem. It is known, however, that the minimum and maximum triangle areas can occur O(n²) and O(n) times, and both bounds are tight. We pursue the analogous problems in the space, and find bounds on the maximal number of unit, minimum, and maximum volume tetrahedra determined by n points in three dimensions, along with some new techniques.

CATHERINE YAN, Texas A&M University, College Station, TX 77845, USA
Crossings and Nestings of Chord Configurations [PDF]

Put 2n points on a circle, then join them in pairs by n chords. It is well known that the number of non-crossing configurations is [ 1/(n+1)]((2n) || (n)), the n-th Catalan number. A natural extension is to enumerate all configurations by the number of crossings of the chords, and it is proved that the distribution of number of crossings is identical to that of nestings. In this talk we extend the above result. We introduce the notion of crossing number and nesting number for a chord-configuration, and prove that these two statistics are distributed symmetrically over all chord configurations. A similar result also holds over all set partitions.