Proceedings, 20th Annual Fall Workshop on Computational Geometry, Oct 29-30, 2010

Hosted by the Center of Excellence in Wireless and Information Technology and the Simons Center for Geometry and Physics.

Sponsored by the National Science Foundation and the Department of Applied Mathematics and Statistics, Stony Brook University.

Friday, October 29, 2010: CEWIT Building, Room 200

[9:00-9:15] ``Resilient and Low Stretch Routing Through Embedding into Tree Metrics,'' Dengpan Zhou and Jie Gao

[9:15-9:30] ``Robust Coverage under Uncertainty in Wireless Sensor Networks,'' Khuong Vu and Rong Zheng

[9:30-9:45] ``Spherical Representation and Polyhedron Routing for Load Balancing in Wireless Sensor Networks,'' Xiaokang Yu, Xiaomeng Ban, Wei Zeng, Rik Sarkar, Xianfeng Gu, and Jie Gao

[9:45-10:00] ``Spanning Properties of Graphs Induced by Directional Antennas,'' Mirela Damian and Robin Flatland

[10:00-10:15] ``Animal Testing,'' Adrian Dumitrescu and Evan Hilscher

[10:15-10:45] Break.

[10:45-11:00] ``Kinetic Minimum Spanning Circle,'' Erik D. Demaine, Sarah Eisenstat, Leonidas J. Guibas, Andr\'e Schulz

[11:00-11:15] ``Fat Voronoi Diagrams,'' Gary L. Miller, Todd Phillips, and Donald R. Sheehy

[11:15-11:30] ``Minimum-Link Problems Revisited,'' Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski

[11:30-11:45] ``Computing Convex Hulls Using Smart Pixels,'' Paul Accisano and Alper \"Ung\"or

[11:45-12:00] ``The Length of the Longest Edge in Multi-dimensional Delaunay Graphs,'' Esther M. Arkin, Antonio Fern\'andez Anta, Joseph S. B. Mitchell, and Miguel A. Mosteiro

[12:00-1:15] Lunch and Poster Session in Lobby, CEWIT

[1:15-1:30] ``An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles,'' Danny Z. Chen and Haitao Wang

[1:30-1:45] ``Convex Transversals,'' Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk and Shang Yang

[1:45-2:00] ``(Probabilistic) Adjustable Range Restricted Strip Cover,'' Amotz Bar-Noy and Ben Baumer

[2:00-2:15] ``On the Complexity of Guarding Problems on Orthogonal Arrangements,'' Ning Xu and Peter Brass

[2:15-2:30] Break.

[2:30-3:30] Invited Talk: ` `Origami Robots and Star Trek Replicators,'' Erik D. Demaine (MIT). ({\em Distinguished Lecture Series}, Computer Science)

[3:30-4:00] Coffee Break, Reception.

[4:00-4:15] ``Minimum Vertex Cover in Rectangle Graphs,'' Reuven Bar Yehuda, Danny Hermelin, and Dror Rawitz

[4:15-4:30] ``Witness Rectangle Graphs,'' Boris Aronov, Muriel Dulieu, and Ferran Hurtado

[4:30-4:45] ``Witnessed k-Distance,'' Leonidas Guibas, Quentin Merigot, and Dmitriy Morozov

[4:45-5:00] ``Constrained Tri-Connected Planar Straight Line Graphs,'' Mashhood Ishaque, Diane L. Souvaine, Csaba D. T\'oth, and Andrew Winslow

Saturday, October 30, 2010: S-240, Basement of Mathematics

[9:00-9:15] ``Extracting the Minkowski Sum Boundary from the Reduced Convolution,'' Evan Behar and Jyh-Ming Lien

[9:15-9:30] ``Maximal $f$-vectors of Minkowski Sums of Large Numbers of Polytopes,'' Christophe Weibel

[9:30-9:45] ``Johnson-Lindenstrauss Dimensionality Reduction on the Simplex,'' Rasmus J. Kyng, Jeff M. Phillips, and Suresh Venkatasubramanian

[9:45-10:00] ``(Non-)Equiprojectivity and (Non-)Biprojectivity of Simplicial Polyhedra,'' Masud Hasan

[10:00-10:15] ``Completing River Networks with Only Partial River Observations via Hydrology-Aware ODETLAP,'' Tsz-Yam Lau and W. Randolph Franklin

[10:15-10:45] Break.

[10:45-11:00] ``(Multi)Filtering Noise in Geometric Persistent Homology,'' Donald R. Sheehy

[11:00-11:15] ``Constructive Approximation of Parametric 2-Manifolds,'' Lance Edward Miller, T. J. Peters, and Alexander Russell

[11:15-11:30] ``Discrete Laplace-Beltrami Operator Determines Discrete Riemannian Metric,'' Wei Zeng, Ren Guo, Feng Luo, and David Gu

[11:30-11:45] ``Kinetic Mesh Refinement in 2D,'' Umut A. Acar, Benot Hudson, Duru Turkoglu

[11:45-12:00] ``Even Orientations with Forbidden Pairs and Demands,'' Sarah Cannon, Mashhood Ishaque and Csaba Toth

[12:00-2:00] Lunch and Open Problem Session.

[2:00-3:00] Invited Talk: ``Hyperbolic Geometry, Conformal Maps and Optimal Meshing,'' Christopher J. Bishop (Stony Brook University).

[3:00-3:30] Break.

[3:30-3:45] ``Geometric Aspects of Robotic Mapping and Monitoring of Data Centers,'' Chris Mansley, Jonathan Connell, Canturk Isci, Jonathan Lenchner, Rajarshi Das, and Jeffrey O. Kephart

[3:45-4:00] ``Approximating Minimum Bending Energy Path in a Simple Corridor,'' Jinhui Xu, Lei Xu, and Yulai Xie

[4:00-4:15] ``Towards a Mathematics of Terrain,'' W. Randolph Franklin

[4:15-4:30] ``Better Upper Bounds on the Rank of the 3D Rigidity Matroid of a General Graph,'' Jialong Cheng and Meera Sitharam

[4:30-4:45] ``Minimum Separating Circle for Bichromatic Points by Linear Programming,'' Yam Cheung and Ovidiu Daescu

[4:45-5:00] ``A New Geometric Algorithm for the Maximum Density Segment Problem,'' Md. Shafiul Alam and Asish Mukhopadhyay

Posters: 20th Annual Fall Workshop on Computational Geometry

``The Joint Recognition Problem: from CAD Constraints to Kinematic Joints,'' Audrey Lee-St.John and Rittika Shamsuddin

``Improved Lower Bound for the Stretch Factor of Delaunay Triangulations,'' Ge Xia and Liang Zhang

``The Discrete 2-Center Problem in $\Re^3$,'' Steven Bitner, Ovidiu Daescu, and Anastasia Kurdia

``Inversion of Quadratic B\'ezier Triangles,'' Gary L. Miller, Matthew Mirman, and Todd Phillips