|
Organizers |
Protein Docking using Elevation
by
Pankaj K. Agarwal
Duke University
Given a smoothly embedded 2-manifold in 3-space, we define the elevation of a point as the height difference to a canonically defined second point on the same manifold, which is invariant under rigid motions. Elevation is used to define features such as lines of discontinuous or continuous but non-smooth elevation on surfaces. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions on molecular surfaces. By aligning these features on protein surfaces we present an efficient algorithm to generate a reasonably small but reliable set of coarse protein docking configurations, and then use an iterative algorithm to locally improve the docking configuration. A protein is considered as a rigid body in our approach, and the output produced can serve as input data for other local improvement methods that allow protein flexibility. We demonstrate the performance of our algorithm by testing our algorithm on a diverse set of protein complexes from the Protein Data Bank.
Date received: February 6, 2005
Points and Combinatorics
by
Oswin Aichholzer
TU Graz, IST
A finite point set in the Euclidean plane is the underlying structure for many problems in discrete geometry. For several questions only their combinatorial properties have to be considered and so-called order types are a common tool to provide these combinatorial structure.
In this talk we report on a complete and reliable data base of all realizable order types in the plane (that is, planar point sets) of cardinality up to 11. Moreover we present a novel and efficient method for a complete extension to order types of larger cardinality in an abstract sense, that is, without the need to store or realize the sets.
Based on these results in the second part we present applications of this data base to various problems from discrete geometry. Questions concerning intersection properties, convexity, triangulations, polygonization, and others are addressed. This includes classic problems like searching for (empty) convex k-gons (happy end problem), decomposing sets into convex regions, counting structures like triangulations or pseudo-triangulations. As an outstanding result we have been able to determine the exact rectilinear crossing number for up to n=17 and slightly improved their asymptotic upper bound.
Date received: March 20, 2005
Orthogonal Surfaces in Four and More Dimensions
by
Stefan Felsner
TU Berlin
Coauthors: Sarah Renkl
Orthogonal surfaces in 3-D are quite well understood. Mild nondegeneracy conditions allow to set them in correspondence to Schnyder woods and 3-connected planar graphs.
In higher dimensions the orthogonal surfaces with a generator set in general position are in a similar correspondence to simplicial polytopes.
Our aim is to understand larger classes of orthogonal surfaces. Some progress and some related problems are the topic of this talk.
Date received: March 21, 2005
The Nesterov rounding and perfectly centered polytopes
by
Komei Fukuda
Swiss Federal Institute of Technology, Zurich and Lausanne
Coauthors: Christophe Weibel
Recently Y. Nesterov has shown that any convex body can be rounded very rapidly by taking the Minkowski sum of itself with a properly scaled dual. More specifically, the asphericity (the ratio of the outer radius over the inner radius) reduces to at least its square root. The purpose of our study is to obtain a combinatorial counterpart of the Nesterov rounding. In particular, we determine the face lattice of the Nesterov rounding applied to perfectly centered convex polytopes. Here, we say a convex polytope perfectly centered if every nonempty face intersects with its outer normal fan. We give closed formula for special cases including perfectly centered simplices and hypercubes. Our final goal is to understand the complexity of the Minkowski sum of several convex polytopes.
Date received: February 3, 2005
Linear Programming and Unique Sink Orientations
by
Bernd Gärtner
Institute of Theoretical Computer Science, ETH Zürich, CH-8092 Zürich, Switzerland
Coauthors: Ingo Schurr
I will introduce the framework of unique sink orientations (USO) as a new tool for dealing with linear programs (LP). For certain LP, the USO approach yields the fastest known deterministic combinatorial algorithm. We also obtain a unique canonical solution for any LP, even in the unbounded or the infeasible case. Connections to quadratic programs and certain linear complementarity problems will be pointed out
Date received: January 17, 2005
Strong General Position for Simplicial Complexes
by
Troy L. Goodsell
Brigham Young University-Idaho
In this paper we consider the concept of Strong General Position for simplicial complexes. We will define what is meant by strong general position and provide a proof of an inequality providing a bound on the number of disjoint simplexes in the complex that an affine plane may intersect. The proof handles the finite dimensional cases and then is generalized to the infinite dimensional case and to separable Hilbert Spaces. We will also discuss applications and examples.
Date received: March 28, 2005
Revlex-Initial 0/1-Polytopes
by
Volker Kaibel
TU Berlin
Coauthors: Rafael Mechtel
We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers f(d, n) of facets and the minimum average degree g(d, n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy f(d, n) £ 3d and g(d, n) £ d + 8. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.
Date received: November 19, 2004
On the vacancy phenomenon in finite sphere packings
by
Wlodzimierz Kuperberg
Auburn University, Auburn, Alabama, U.S.A.
What is the minimum radius rn(k) of a spherical container in Rn that can hold k unit balls? The exact answer is known only in a few cases. For n > 2, all of the solved cases are essentially due to R.A. Rankin (1955), and they are limited to k £ 2n. However small this number of cases is, some of them display an interesting phenomenon: the value of rn(k) can remain constant for several consecutive values of k (with n fixed). In other words, it can happen that if a spherical container is large enough to accommodate k unit balls, then there is still room in it for a few more. Specifically, Rankin's result is that rn(n+2)=rn(2n), which shows that, for sufficiently large n, the vacancy ratio [m/(k+m)], associated with the occurrence of rn(k)=rn(k+m), can be arbitrarily close to [1/2]. Here we prove that this ratio cannot reach [1/2], for any n. We then discuss the same phenomenon for packing balls, or translates of another body, in convex containers of various shapes.
Date received: March 11, 2005
All rational convex polytopes are 3-way transportation polytopes
by
Jesus De Loera
Univ. of California Davis
Coauthors: Shmuel Onn (Technion Haifa)
In this talk we discuss the following theorem:
Any rational convex polytope is polynomial-time representable as a 3 ×r ×c line-sum transportation polytope. This universality result has important consequences in discrete optimization and statistics.
Date received: November 24, 2004
Valuations on Simplices
by
Monika Ludwig
Institut f. Diskrete Mathematik und Geometrie, TU Wien
Coauthors: Matthias Reitzner
A function mu: S ® R defined on a class
S of sets is called a valuation if
|
Here the question is asked whether a valuation only defined on simplices can always be extended to a valuation on convex polytopes. The answer is yes and the proof combines classical tools from algebraic topology with a shelling type argument.
Date received: February 4, 2005
Volume bounds for lattice tetrahedra
by
Julian Pfeifle
Universitat Politècnica de Catalunya
Coauthors: Bruce Reznick, Christian Haase
Douglas Hensley was the first to prove that for each d and k there exists a constant V(d, k) such that the volume of any d-dimensional lattice polytope that contains k interior lattice points is at most V(d, k). In this talk, we will prove the optimal value V(3, k)=12k+8 for the special case of lattice tetrahedra with empty facets that contain k interior lattice points.
Date received: November 19, 2004
A New Methodology in Geometric Transversal Theory
by
Ricky Pollack
Courant Institute
Coauthors: Jacob E. Goodman
We describe a new encoding of a family of mutually disjoint compact convex sets that captures many of its combinatorial properties and use it to give a new proof of the Edelsbrunner-Sharir theorem that a collection of n mutually disjoint compact convex sets in the plane cannot be met by straight lines in more than 2n-2 combinatorially distinct ways. The encoding generalizes our encoding of planar point configurations by "allowable sequences" of permutations. Since it applies as well to a collection of compact connected sets with a specified pseudoline arrangement A of separators and double tangents the result extends the Edelsbrunner-Sharir theorem to the case of geometric permutations induced by pseudoline transversals compatible with A.
Date received: December 2, 2004
Strictly convex drawings of planar graphs
by
Günter Rote
Freie Universität Berlin
Coauthors: Imre Bárány
Every three-connected planar graph with n vertices has a drawing on an O(n2) ×O(n2) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings, which are known to exist on O(n) ×O(n) grids. The proof combines techniques from graph drawing and the geometry of numbers.
Date received: November 19, 2004
Convexity in Polyhedral Spaces
by
Konstantin Rybnikov
University of Massachusetts at Lowell
Some fundamental ideas of convex geometry can be transported to topological spaces without linear structure or Riemann metric - e.g., polyhedral manifolds form an interesting class of examples, although much more general topological spaces could and should be considered in this context. The talk will focus on convex and combinatorial properties of immersed hypersurfaces in polyhedral and more general spaces. Results and conjectures that will be presented will mostly concern extremal structure of locally convex hypersurfaces.
This is a preliminary report on the work in progress.
Date received: March 30, 2005
Pseudo-triangulations, rigidity and planar graphs
by
Francisco Santos
Universidad de Cantabria
Pseudo-triangulations of polygons or planar point sets generalize triangulations and have been studied in Computational Geometry for ten years, with applications in visibility and kinetic data structures, among other things.
A turning point in the study of pseudo-triangulations came in 2000, when Ileana Streinu found very nice coonnections between them and rigidity of plane structures, and used these connections to give a second proof of the Carpenter's Rule Theorem (every simple polygon can be convexified by a continuous motion). Since then, the relation between pseudo-triangulations, planarity and rigidity has been investigated further, giving rise to, for example, the following results:
Theorem (Hass, Orden, Rote, Santos, Servatius, Servatius, Souvaine, Streinu, Whiteley): A planar graph is isostatic (i.e., minimally generically rigid) in the plane if and only if it is the graph of a pointed pseudo-triangulation.
Theorem (Orden, Santos, Servatius, Servatius): A planar graph is generically rigid in the plane if and only if it is the graph of a pseudo-triangulation.
Date received: February 7, 2005
Counting crossing-free configurations in the plane
by
Micha Sharir
Tel Aviv University
Coauthors: Emo Welzl
We derive improved upper and lower bounds on the number of crossing-free configurations of various kinds that are determined by a set of n points in the plane. For example, we show that the number of crossing-free perfect matchings in such a set is 10.52n. We also consider (crossing-free) perfect bipartite matchings, partitions, hamiltonian paths and cycles, and "safe" hamiltonian paths.
Date received: March 8, 2005
Isothetic parallelotopes and the binary intersection property
by
Valeriu Soltan
George Mason University, USA
Let F = {Cl} be a family of convex polytopes in Ed, d ³ 2. We say that F has the strong binary intersection (SBI) property if for any set {vl} of vectors in Ed the family of translates F¢ = {vl + Cl | Cl Î F} has the binary intersection property (Helly number two, in other terminology), i.e., from the fact that any two elements of F¢ have a point in common it follows that the members of F¢ have a point in common. We prove that a family F with at least five members has the SBI property if and only if the members of F are isothetic parallelotopes, i.e., the edges of these parallelotopes are parallel to some d linearly independent directions of Ed.
Date received: November 22, 2004
Halving the colors of a Kneser coloring
by
Francis Edward Su
Harvey Mudd College
Coauthors: Gwen Spencer
Given a (2n+k)-element set P, color the n-subsets of A by k+2 colors so that any pair of disjoint n-subsets have different colors (a Kneser coloring). Then for any partition of the colors into two "halves" C1 and C2 (whose sizes differ by at most 1) there is a partition of P into two sets P1 and P2 whose n-subsets realize the colors (and only those colors) of C1 and C2, respectively, and moreover, both P1 and P2 are at least 1/4 the size of P. This strengthens a 1982 result of Fan. We give two proofs: a topological proof that depends on the Lusternik-Schnirelmann-Borsuk theorem, and a constructive combinatorial proof that depends on Fan's generalization of Tucker's lemma. Finally, we give generalizations for more than k+2 colors and suggest social applications of this result.
Date received: March 15, 2005
On the frontiers of polynomial computations in tropical geometry
by
Thorsten Theobald
TU Berlin, Yale University
We study some basic algorithmic problems concerning the intersection of tropical hypersurfaces in general dimension: deciding whether this intersection is nonempty, whether it is a tropical variety, and whether it is connected, as well as counting the number of connected components. We characterize the borderline between tractable and hard computations by proving NP-hardness and #P-hardness results even under various strong restrictions of the input data, as well as providing polynomial time algorithms for various other restrictions.
Date received: November 22, 2004
k-Sets and Topological Invariants of Plane Curves
by
Uli Wagner
Einstein Institute of Mathematics, The Hebrew University of Jerusalem
A k-set of a finite point set in Euclidean space is a subset of cardinality k that can be spearated from its complement by a hyperplane. These are basic and well-studied objects in discrete and computational geometry, with numerous, and sometimes surprising, relations to other problems, such as Gröbner bases, g-vectors of convex polytopes, or rectilinear crossing numbers of complete graphs. At the same time, a number of fundamental questions are still open, most notably: What is the maximum number of k-sets that an n-point set in d-space can have (where d is considered constant and k, n tend to infinity)? Even in the plane, there remains a wide gap between the currently best lower and upper bounds of n·exp(√{logk}) and nk1/3, respectively. The upper bound is proved by analyzing the number of crossings between objects closely related to k-sets, so-called k-edges (these are pairs of points from the ground set such that the line they span dissects the remaining points into parts of size k and n-2-k, respectively). The collection of k-edges of a point set naturally decomposes into locally convex closed cycles. Motivated by the analysis of crossings, we study other topological invariants of these cycles (interpreted as plane curves), such as the Whitney index (or global winding number) and the so-called J± invariants of plane curves introduced by Arnold' in the early 1990's. The partial results I could obtain so far do not yield any improved bounds for the number of k-sets, but I would like to make the case that this viewpoint is interesting and deserves further study.
Date received: February 8, 2005
Ehrhart polynomial and successive minima
by
Jörg Wills
Universität Siegen
Coauthors: Martin Henk, Achill Schürmann
We investigate the zeros of the Erhart polynomial for centrally symmetric convex bodies and show that there are close relations to Minkowski's successive minima.
Date received: April 5, 2005