Géométrie discrète et convexe
Org: Karoly Bezdek (Calgary) et Jozsef Solymosi (UBC)
- KAROLY BEZDEK, University of Calgary, 2500 University Drive N.W., Calgary,
AB T2N 1N4
On the illumination parameters of smooth convex bodies
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
This is a joint work with A. Litvak (Univ. of Alberta).
- TED BISZTRICZKY, University of Calgary
Transversals and Convex Sets
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
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.
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.
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.
- BOB ERDAHL, Queen's University
Reducible and irreducible Voronoi polytopes for lattices
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
The classical Erdos distance problem says that N points in
Rd 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
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 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.
(i) every roadway of width at least t (independent of its
layout) is guaranteed to have a unit curvature-bounded traversal,
(ii) for any width w < t there exist roadways of width
w that admit no such traversal.
- IZABELLA LABA, University of British Columbia, Vancouver, BC
An incidence theorem for pseudoflats
We prove a Pach-Sharir type incidence theorem for a class of
algebraic curves in Rn and algebraic surfaces in R3.
Joint work with Jozsef Solymosi.
- ZSOLT LANGI, University of Calgary, 2500 University Dr. NW, Calgary, AB
Ball-polytopes and 1-convexity
For points p,q Î Rn, [p,q]1 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]1. 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
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 2n; which bound, if it holds, is sharp as it is
attained by cubes. The previously known bound was 3n which I
improved to 2(n+1).
- SUBHASH SURI, University of California, Santa Barbara, USA
Detecting Cuts in Sensor Networks
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
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
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(n3/2logn) bound on the number of edges with Adam
Marcus, which is almost tight as abstract graphs with
W(n3/2) edges and no C4 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
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(n2) 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
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.