David Eppstein – Publications

Publications with Nodari Sitchinava

• Guard placement for efficient point-in-polygon proofs.
  D. Eppstein, M. T. Goodrich, and N. Sitchinava.
  arXiv:cs.CG/0603057.
  23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 27–36.

  The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.