This is an interesting mathematical challenge to help solve a big business problem. Where to put the cell towers to achieve (say) a 95% coverage of a specific area. By coverage, I mean that 95% of people have signal in the area in question. Also, cell towers do not need to have the same power, and we can play with this to reduce costs.
Typically, such problems are solved using Monte-Carlo simulations, and are considered to be research operations problems. Yet a mathematical solution might be available as well, based on stochastic geometry. For instance, in the picture below, a boolean model for wireless network coverage and connectivity is constructed from randomly sized disks placed at random locations. More can be found here.
The picture below shows SINR cells of a wireless network model expanding as the transmitter powers increase (source: click here.)
Finally, below is a simulation of four Poisson–Boolean (constant-radius or Gilbert disk) models as the density increases with largest clusters in red. Click here for details.
Note that earlier studies used to approximate coverage using hexagons instead of circles, see picture below. However, this does not take into account cell towers with different power, or elevation which indirectly has an impact on how far the signal can reach.
The Wiki for the Stochastic geometry process is close but even then cell tower location determination is a little more complex than you or the Wiki described. It has only touched the surface of the problem....and BTW, I am not an expert, I have picked up some knowledge by working with people who are.
In a flat plane the considerations you provided is generally correct, but in the real world where there is 3D there are more parameters to take into account. Some of which are localized water towers and buildings blocking the signals or reflecting them (multi-path propagation). Hills and mountains can produce holes and drop points. Individual cell phone manufacturers require different minimum signal levels and even different protocols operate at different frequencies and therefore have different ranges. It may work as designed for a Samsung phone and fail for an iPhone.
Another thing to consider is that each of the multiple antennas per site, since they are directional and not dipole, they have the ability to be moved where the tilt angle from the vertical or horizontal or shifted vertically and can be adjusted when installed to help with these problems. This process changes the shape of the signal that enters/leaves the cell tower from a 3D Gaussian to that of a flower petal as needed.
The radio equipment at the cell tower site has been designed to account for some of these problems such as multi-path reflection signals and signal strength changes by telling the cell phone to increase or decrease its signal level as well as its own to some optimal value. Remember the signal level is a gradient value that falls off over distance. Since the power level of the RF can change along with the receiver sensitivity, some of the RF holes that people fall into are not quite as much of a limitation as they could be. The manufacturer of the cell phone is as much a factor as anything else.
One last thing to consider is that cell towers are designed and placed to have some overlap to allow for complete coverage. As the cell phone moves from one point to another (example: cars on a highway), one tower performs a hand-off to a different tower as the signal strength fades from one tower but is increasing from another tower. In the newer phones, it is the phone that determines when the handover occurs and not the tower.
Finally, you may not get the location that you want for placing your tower. It may already be occupied by a building, lake, airport...etc.
All in all, mathematics can only get you so far. After that, localization and antenna setup cause the process to become an "art" proven by taking empirical data by driving around and making phone calls and checking signal strength.
Remark: the corresponding deterministic problem (with full coverage) is equivalent to the four color problem. If somebody is interested in the the details pls. let me know and I will elaborate.
I am interested in the relation to the 4 color problem. When you get a chance, please elaborate.