DIMACS DCI 2002

July 18, 2002

 

REU Abstracts

 


Students

Jakub Cerny, Charles University, Czech Republic

jcerny@dimacs.rutgers.edu

Zdenek Dvorak, Charles University, Czech Republic

dvorak@dimacs.rutgers.edu

Vit Jelinek, Charles University, Czech Republic

vjelinek@dimacs.rutgers.edu

Pavel Podbrdsky, Charles University, Czech Republic

ppod@dimacs.rutgers.edu

Mentors

Janos Komlos, Department of Mathematics

Martin Mares, Charles University


On the Polygon Crossing Problem

Let k, l ≥ 3 be integers. Consider two polygons in a plane with k and l vertices respectively. We are interested in the problem of determining the maximum possible number of intersections of their boundaries for given k and l. Denote this maximum by f(k,l). When k and l are both even, it is easy to show that f(k,l)=kl. If k is even and l is odd then f(k,l)=k(l −1). However, if k and l are both odd the problem seems extremely difficult and the exact value of f(k,l) is unknown. In this last case, if kl then (k −1)(l −1) + 2 ≤ f(k,l) ≤ (k − 1)l. The hypothesis is that the lower bound is tight. This hypothesis is proved for the cases k=3 and k=5. In this talk we present the methods used to improved the upper bound to obtain f(k,l) ≤ kl − l −(k −3)/2.


 

Student

Samuel Stechmann, University of ST. Thomas, MN

sam@dimacs.rutgers.edu

Mentor

Mathew Leingang, Department of Mahtematics

Hilbertís 3rd Problem and Hyperbolic Geometry

 

Two polygons are scissors congruent if one of them can be cut up into polygon pieces and put back together to form the other.Clearly if two polygons are scissors congruent, then they have the same area.The converse, i.e. if two polygons have the same area then they are scissor congruent, is also true.Hilbertís 3rd Problem asks the analogous question in three dimensions:If two polyhedra have the same volume then are they scissors congruet?Hilbertís student Max Dehn provided a counterexample to show that equal volume does not imply scissors congruence in Euclidean geometry.Hilbertís 3rd Problem in hyperbolic geometry, however, has yet to be solved.

 


 

Student

Yuki Saka, University of California at Berkeley, CA

ysaka@dimacs.rutgers.edu

Mentors

Leonid Khachiyan, Department of Computer Science


A Generalization of Spanning Trees and Cuts

 


 

Student

Paul Gross, Rose-Hulman Institute of Technology, IN

pgross@dimacs.rutgers.edu

Mentors

Eric Allender, Computer Science Department


Extracting a Sequential Algorithm for Solving the Planarity Problem

 

A planar graph is a graph that can be drawn in the plane such that no two edges intersect.The Planarity Problem is to determine if a given graph is planar and if so to provide a planar embedding of the graph.An efficient parallel algorithm for solving the Planarity Problem will be mentioned and the project goals of the student.