Archive for the ‘Discrete Geometry’ Category
Journal of Computational Geometry
What does it cost to run an open access journal? The Journal of Computational Geometry recently released their financial statements of the past three years.
http://jocg.org/index.php/jocg/announcement
Of course there’s a lot of freely donated labour that’s makes this possible, but non-free journals get similar donations.
3 X 3 Reuleaux triangles
Update 25th September 2009: for a very similar picture, see this post by David Eppstein.
[The piece below used to lie around on my homepage since April 2007. I'm slowly closing down that site, as the party is over at Google's Page Creator.]
The picture above is something that came out of my work with Achill Schürmann. It is used to disprove a conjecture of Gary Lawlor and Frank Morgan. Read the rest of this entry »
New Look
I’ve changed the look of my blog. And it now subsumes my homepage. I’ll take that homepage down soon as google page creator seems to be on the verge of going down (or at least, on the verge of being moved to google sites, which doesn’t seem as nice to me).
Points and lines
Terry Tao has a great post about the Szemeredi-Trotter theorem on the maximum number of incidences between m points and n lines in the plane. Also read Jozsef Solymosi’s insightful comment.
Some musings around Borsuk’s conjecture
Borsuk conjectured in 1933 that any bounded subset of n-dimensional Euclidean space can be partitioned into n+1 parts, all of smaller diameter. An equilateral simplex shows that that you need at least n+1 parts. The famous Borsuk-Ulam theorem can be formulated as saying that you also need at least n+1 parts for the Euclidean (n-1)-sphere. (Note that n+1 parts also suffice for the sphere.)
Borsuk’s conjecture is true in dimensions 2 and 3. In 1993 Kahn and Kalai proved that the conjecture is false if the dimension is sufficiently large. For a short explanation by Gil Kalai, click here. For a wonderful (very) short story on how their proof came about, click here. The lowest dimension for which it is currently known that the conjecture fails is n=298, due to Aicke Hinrichs and Christian Richter.
It is not so difficult to prove the 2-dimensional case. The 3-dimensional case, first proved by Eggleston, is somewhat messy. A short proof for finite sets in 3-space was found by Heppes and Revesz (1956). It goes as follows.
The number of diameter pairs in a set S of n points in 3-space is at most 2n-2. (A diameter pair of S is a pair of points in S whose distance equals the diameter of S.)
Therefore, the diameter graph of S has average degree at most 4-4/n. So we can always find a point incident to at most 3 diameters of S.
So we can greedily 4-colour the graph.
The colour classes give the partition!
Problem: Can this argument be modified easily to also work for infinite sets? For example, a solution to the following problem would imply Eggleston’s theorem:
Show that there exist 
Here we define G of almost-diameter pairs to be the graph on S with edges all pairs of points at distance at least 
In general, it is not clear how to go from finite sets to general bounded sets. So it is “conceivable” for example that the conjecture holds for all finite sets in 4-dimensional space, but not for all bounded sets….
How to lower your Erdös number to 1.
Many mathematicians, mostly those of a combinatorial bent, are very interested in their and others’ Erdös numbers. It’s clearly impossible to get an Erdös number of 1 if you are not already there. Or is it?
By the way, according to MathSciNet, Erdös has dozens of posthomous papers, the newest having appeared in 2008….
Tverberg’s theorem
At Combinatorics and More, Gil Kalai has a nice explanation of the beautiful theorems of Helly, Radon, Carathéodory, and Tverberg (here and here). I’m looking forward to the next installment.
The Steiner problem in normed spaces III
The formulation
Finally, let’s make a precise formulation of the Local Steiner problem. Read the rest of this entry »
The Steiner problem in normed spaces II
Other norms
In part I I discussed the Steiner problem in the Euclidean plane. Here I give an overview of various normed spaces for which geometric Steiner minimal trees have been considered. This motivates the study of Steiner minimal trees in arbitrary (finite-dimensional) normed spaces.
The Steiner problem in normed spaces I
The Euclidean Steiner problem
What is the shortest network that interconnects the three vertices of an equilateral triangle of edge length 1? Any pair of edges of the triangle form a minimal spanning tree of the three points. This tree has total length 2, but it is not the shortest.
