City Guarding and Path Checking: Some Steps Towards Smart Cities




Journal Title

Journal ISSN

Volume Title



With drones and other small unmanned aerial vehicles starting to get permission to fly within city limits, monitoring the aerial space of big cities is becoming a critical problem that yet has to be addressed. While video cameras are easily available in most cities, their purpose is to guard the streets at ground level. Guarding the aerial space of a city with video cameras is a problem that so far has been largely ignored even in a limited way of all three dimensions. In this dissertation, we address various issues that set a necessary foundation for drone surveillance, which are as follows:

  1. City Guarding with Limited Field of View.
  2. Path Checking in < 2 In the first problem, we present bounds on the number of cameras needed to guard a city’s aerial space (roofs, walls, and ground) using cameras with 180◦ range of vision (the region in front of the guard), which is common for most commercial cameras. Each camera is placed at the top corner of a building. We considered the following cases:
  3. All buildings are vertical and have a rectangular base.
  4. All buildings are vertical and have an orthogonal base. For each case, we further considered the following two sub-cases:
  5. Buildings have an axis-aligned ground base and,
  6. Buildings have an arbitrary orientation. Unlike previous studies on guarding polygons with holes, a key subproblem we encounter is to guard a simple shaped polygon with holes by placing guards only at the vertices of the holes. We further address the following path checking problem: Given a set S of m disjoint simple polygons in the plane, with a total of n vertices, preprocess them so that for a query consisting of a positive constant c and a simple polygonal path π with k vertices, from a point u to a point v in free space, where k is much smaller than n, one can quickly decide whether π has clearance at least c (that is, there is no polygonal obstacle within distance c of π). To do so, we show how to solve the following related problem: Given a set S of m simple polygons in < 2 , preprocess S into a data structure so that the polygon in S closest to a query line segment s can be reported quickly.



Smart cities, Cities and towns ǂx Effect of technological innovations on, Drone aircraft