An uninflatable polyhedron
|
An uninflatable polyhedron |
· Home · Course Announcement · Schedule · Homeworks · References · Administrivia ·
I will add one-paragraph summaries to each proposal over the next few days.
Project Problems
- Amir Nayyeri: Selfish greedy routing in sensor networks
Consider a geometric graph in which nodes represent hosts and edges represent network links. A greedy path is a path from some node s to some other node t, such that the distace to t decreases monotonically along the path. A greedy embedding of an abstract graph is an assignment of coordinates to the vertices, so that every pair of nodes is connected by a greedy path (in both directions)—the coordinates may have no relationship to the actual locations of the hosts they represent. Papadimitriou and Ratajczak [Theoretical Computer Science 2005] conjectured that every 3-connected planar graph has a greedy embedding; Dhandapani [SODA 2008] proved that every planar triangulation has a greedy embedded, but his proof is nonconstructive. Now suppose the nodes are independent, selfish agents who each want to maximize the number of other nodes to which they have greedy paths. Let g(s) denote the number of nodes t such that there is a greedy path from s to t. In an equilibrium embedding, no node s can increase g(s) by changing its coordinates. Do equlibrium embedings exist?- Aparna Sundar: Checking Euclidean minimum spanning trees
Suppose we are given a straight-line drawing T of a tree in the plane, with n vertices. Is there a simple and robust algorithm to determine in o(n log n) time whether T is the Euclidean minimum spanning tree of its vertices? We can easily verify EMSTs in O(n log n) time by recomputing them from scratch via the Delaunay triangulation. Is there a faster algorithm? Surprisingly, this problem is open even in the special case where T is a simple polygonal path.- Charles Blatti: Shortest paths in line arrangements
Is there a sub-quadratic algorithm to compute shortest paths between two vertices in an arrangment of lines? Any finite set of lines partitions the plane into a complex of convex cells; this cell complex is called the arrangement of the lines. We are interested in paths in the planar graph of vertices and edges of this arrangement. This graph has quadratic complexity and can be constructed in O(n2) time. Thus, shortest paths can be computed in O(n2) time using the planar shortest-path algorithm of Henziger et al. Subquadratic shortest path algorithms are known for some special cases—lines in few parallel families, or the union of two pencils. There is also an approximation algorithm that runs in O(n log n) time. Do these special-case algorithms still work if the lines are weighted?- Dan Screiber: Convex hulls of imprecise points
Compute the `best' convex hull of a set of imprecise points in the plane. An imprecise point is specified by a simple region in the plane, such as a circle, square, or rectangle. Each point is known to lie somewhere inside its correspinding region, but the exact location is unknown. The goal is to compute a convex polygon that intersects each of these regions and optimizes some other criterion, such as maximum area, minimum perimeter, or minimum number of edges.
- Evan VanderZee: Acute triangulations through Delaunay refinement
In a very recent paper, Hale Erten and Alper Üngör proposed a variation of the off-center Delaunay refinement algorithm that either outputs an acute-angled well-spaced triangulation or loops forever. Does Erten and Üngör's algorithm always halt?
- Hui Kong: Bus sequencing for escape routing in PCBs
- Jingjin Yu: Mesh geeration using van der Corput sequences
- Kamilah Taylor: 3D curve reconstruction via moving-least-squares
- Leonardo Bobadillo: On-line search in easily guardable polygons
- Mahsa Kamali: Reconstructing trees using L-systems by shape analysis/indexing
- Pratik Worah: Dynamic and fault-tolerant spanners
- Shen-Fu Tsai: Reconstructing point sets from their Voronoi vertices
- Tan Yan: Length-matching routing with given topology