Workshop on Geometric Problems on Sensor Networks and Robots

June 8-June 12, 2015

organized by Peter Brass (CCNY) and Jon Lenchner (IBM Research)

supported by NSF grant CCF 1017539

The aim of this workshop is to discuss and solve geometric problems related to sensor networks or robotics. The plan is to come together for one week, and each day from 9.30am to 6.00pm propose problems and attempt to solve them.

Workshop Participants

• Hugo Akitaya (Tsukuba University) hugoakitaya@gmail.com
• Habib M. Ammari (University of Michigan at Dearborn) hammari@umd.umich.edu
• Esther Arkin (Stony Brook University) esther.arkin@stonybrook.edu
• Huck Bennett (New York University) hbennett@cs.nyu.edu
• Peter Brass (City College New York) peter@cs.ccny.cuny.edu
• Yi-Jen Chiang (New York University) chiang@nyu.edu
• Alon Efrat (University of Arizona) alon@cs.arizona.edu
• Sylvester Eriksson-Bique (New York University) ebs@cims.nyu.edu
• Jie Gao (Stony Brook University) jgao@cs.stonybrook.edu
• Mayank Goswami (Max Planck Institut Saarbrücken) gmayank@mpi-inf.mpg.de
• Matthew Johnson (Lehman College) mpjohnson@gmail.com
• David Kirkpatrick (University of British Columbia) kirk@cs.ubc.ca
• Elmar Langetepe (University of Bonn) elmar.langetepe@informatik.uni-bonn.de
• Jon Lenchner (IBM Research Yorktown Heights) lenchner@us.ibm.com
• Joe Mitchell (Stony Brook University) jsbm@ams.stonybrook.edu
• Eli Packer (IBM Research Haifa) elip@il.ibm.com
• Anika Rounds (Tufts Univ) Anika.Rounds@tufts.edu
• Jack Snoeyink (NSF and University of North Carolina at Chapel Hill) jsnoein@nsf.gov
• Kiril Solovey (Tel Aviv University) kirilsolo@gmail.com
• Csaba Toth (California State University Northridge) cdtoth@eecs.tufts.edu
• Chee Yap (New York University) yap@cs.nyu.edu
• Jiemin Zeng (Stony Brook University) jieminzeng@gmail.com

The conference hotel is the Holiday Inn in Mt Kisco. We will provide van service between the Holiday Inn and the conference location, which will be in the IBM Research Lab in Yorktown Heights. See here how to get to the Yorktown Heights lab.

Problems

1. Guarding Segments in a Box, in many variants (Jon Lenchner) Notes by Jon Lenchner
2. r-gather problem: clustering points so that each cluster contains at least r points, and the maximum diameter is minimized (Jiemin Zeng)
3. Guard Network: place guards in a polygon so that the entire polygon is seen, the r-distance network of the guards is connected, and the number of guards is minimized (Jie Gao) Notes by Jie Gao
4. Optimal Lawnmower Paths in a Square: what is the closed shortest path in a square of sidelength L such that each point of the square has distance at most 1 to the path (Peter Brass)
5. Moving Two Square Robots in an Orthogonal Polygon: the robots should not overlap during the motion (Hugo Akitaya)
6. Approximate Shortest Path for a Disk among Obstacles in the Subdivision Model (David Kirkpatrick)
7. Pre-emptive Strategies for Smoothing in Quad-Tree like structures (Chee Yap)
8. Deciding Optimality of a Lawnmower Path (Huck Bennett) Notes by Huck Bennett
9. Placing Sensors to Minimize Uncertainty Regions (Eli Packer) Notes by Eli Packer
10. Watchman Routes in 3D (Joe Mitchell)
11. 231-free grid Point Problem (Mayank Goswami)
12. Placing Sensors to detect primary and secondary transmitters (Alon Efrat)
13. Placing Isolation Guards (Joe Mitchell)

Further Photos from the Workshop

Peter Brass (peter@cs.ccny.cuny.edu or phjmbrass@gmail.com)