Planning Points on the Plane with Geometric Constraints
Department of Systems and Computer Engineering, Carleton University

The study and planning of cellular towers on an urban map is full of interesting computational geometry problems.

Part 1: topics in stochastic geometry: random point processes. We consider random points deployed on a plane, and examine statistical metrics to characterize their spatial regularity. We use this knowledge to design good point processes with tunable regularity, with various applications in planning point sets on a plane with maximal regularity (repulsiveness).

Part 2: an approximate art gallery problem with polygonal holes. Given the layout of a city’s buildings as polygonal footprints, we consider how to cover the maximum of the outdoor area with the minimum number of wall-mounted cellular access points.

Part 3: extensions to other applications. Automated partitioning of urban maps into meaningful components connected in a graph. Optimal planning with constraints of punctual and linear resources on an urban map.