Program

Abstract 
of the Talks

Participants

Contact

UNT Campus Map

Title: Directions in Discrete Geometry
Speaker: János Pach

Abstract: 
In the past ten years, Erdos-type extremal problems on the maximum number of incidences between points and lines, and various other geometric objects have turned out to be intimately related to important questions in additive number theory (Szemeredi's and Freiman's theorems on arithmetic progressions), in analysis (Kakeya's problem), in combinatorics (designs, finite projective planes), and found many applications in computer science (motion  planning). The recent work of Bourgain, Gowers, Tao, Wolff, and others opened new directions of research. After a quick overview of these developments, we concentrate on a few specific elementary problems in discrete geometry, related to the number of different directions induced by a point set.

According to a celebrated theorem of Sylvester and Gallai, any finite set S of non-collinear points in the plane has two elements whose connecting line does not pass through any other point in S. Erdos noticed that this result immediately implies that any set of n non-collinear points in the plane determines at least n different connecting lines. Equality is attained if and only if all but one of the points are on a line. In the same spirit, Scott posed two similar questions in 1970: (1) Is it true that the number of different directions assumed by the connecting lines of n > 3 non-collinear points in the plane is at least n-1? (2) Is it true that the number of different directions assumed by the connecting lines of n > 5 non-coplanar points in 3-space is at least 2n-3?

The first question was answered in the affirmative by Ungar in 1982, using allowable sequences. Recently, Pinchasi, Sharir, and the speaker solved the second problem of Scott. 

------------------------------------------------------------------------------ 
 
 

Title: Geometric Approximation Using Core Sets
Speaker: Pankaj K. Agarwal

Abstract: 
This talk presents a general technique for approximating the `extent'' of a set of points in d-dimensional space.  Extent is an abstraction that
includes as special cases the diameter, width, and smallest bounding box, ball, or cylinder.  For a given tolerance epsilon>0, the technique
computes a ``core'' subset of the input points that approximates the extent of the whole set.  The size of the core-set  depends upon epsilon but is independent of the size of the input set, and for any fixed epsilon, the core-set can be computed in linear time.  The technique
extends to maintaining an approximation of the extent of moving points and to points given online in the streaming model. The technique also allows fitting various shapes, including spheres and cylinders, through a point set. Various extensions of this technique and open problems are also discussed.

Joint work with Sariel Har-Peled and Kasturi Varadarjan.
                    ------------------------------------------------------------------------------ 

Title: Edge weights and vertex colours
Speaker: Michal Karonski

Abstract: 
A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. Such a weighting induces a vertex coloring, i.e., by assigning the same color to  vertices with the same weight.

An assignment of positive integer weights to the edges of a simple graph G is called irregular if the weighted degrees of the vertices are all different, i.e., the induced vertex coloring is trivial. The irregularity strength, s(G), is the maximal weight, minimized over all irregular assignments, and is set to infinity if no such assignment is possible.

In the first part of my talk  I will discuss results from a recent paper [1] where we show that s(G) <=  c_1 n / d, for graphs with maximum degree D <= n^{1/2}, and s(G) <= c_2 (log n) n / d, for graphs with 
D > n^{1/2}, where c_1 and c_2 are explicit constants, and d denotes minimum degree of G.

It is natural to consider edge weightings where we require only that
adjacent vertices have different weights --- that is, the  vertex weighting induce a proper colouring of the graph. In this context,  in [2] we raise the following question, in which a ``non-trivial graph'' refers to a connected graph with at least three vertices.

Question: Is it possible to weight the edges of any non-trivial graph with the integers 1,2,3 such that the resultant vertex weighting is a proper colouring?

In the second part of my talk I will offer two pieces of information, given in [2], in relation to the above  question:
first, that a weighting is possible for 3-colourable graphs, and secondly
that, if real, rather than just integer, weights are permitted, then a finite number of weights suffices for all graphs.
To prove all results in [1] and [2], we are using  a combination of 
deterministic and probabilistic techniques.

References
[1] R.J. Gould, A. Frieze, M. Karonski and F. Pfender, On graph irregularity strength, Journal of Graph Theory, 41 (2002) 120--137.
[2]M. Karonski, T. Luczak, A. Thomason, Edge weights and vertex colours, submitted.
                    ------------------------------------------------------------------------------ 

Title: On Polyhedra Induced by Point Sets in Space
Speaker: Godfried Toussaint

Abstract: 
Given a set S of n points in the plane (not all on a line) it is well known that it is always possible to polygonize S, i.e., construct a simple polygon P such that the vertices of P are precisely the given points in S. In 1994 Grunbaum showed that an analogous theorem holds in 3-dimensional space. More precisely, if S is a set of n points in space (not all of which are coplanar) then it is always possible to polyhedronize S, i,e., construct a simple (sphere-like) polyhedron P such that the vertices of P are precisely the given points in S. Grunbaum's constructive proof may yield Schonhardt polyhedra that cannot be triangulated. In this talk several alternative algorithms for constructing such polyhedra induced by a set of points will be presented. The methods yield polyhedra which not only may always be triangulated, but which enjoy several other useful properties as well. Such properties include polyhedra that are, terrains, star-shaped, have hamiltonian skeletons, and admit efficient point location queries.
Furthermore, it will be shown that polyhedronizations with a variety of such useful properties can be computed efficiently in O(n log n) worst-case time.

This is joint work with Ferran Hurtado and Joan Trias of the Universidad Politecnica de Catalunya, Barcelona.

------------------------------------------------------------------------------