I have recently been looking at some facility location problems and how they change in the presence of the motorway (or highway, freeway) etc. Tried to visualize some observations with the Voronoi diagrams. But doing it by hand becomes extremely tedious when the number of points increases. Wanted to ask for some recommendation of the software that might do the trick? Looking for a software that would allow for L1 and L2 metrics but it would be nice if could also do a general Lp. Was curious if there is a simple "go to" software among OR researchers or does everyone do it on their own?

  • 1
    $\begingroup$ You can use scipy for $L_2$. $\endgroup$
    – Kuifje
    Jun 13, 2021 at 8:58
  • $\begingroup$ Yes. But what about other metrics? Are they that little researched? $\endgroup$
    – bajun65537
    Jun 13, 2021 at 14:05
  • 1
    $\begingroup$ I'm not sure. Maybe its worth opening an issue on Scipy to ask for this feature. I haven't looked at the source code, but changing metrics is probably not that difficult once you have the whole algorithm set up. $\endgroup$
    – Kuifje
    Jun 13, 2021 at 14:13
  • $\begingroup$ I am confused by L1 and L2 notation here and what they mean exactly. It may be worth perusing the GIS site though. Most GIS implementations that are not standard use raster based statistics, not vector, e.g. gis.stackexchange.com/a/373761/751. $\endgroup$
    – Andy W
    Jun 13, 2021 at 15:57
  • 2
    $\begingroup$ @AndyW Thanks for the R script. I think what you are seeing is in part a function of your choice of p1 and p2. I modified your script to set p1 = (0.5, 0.5) and p2 = (0.7, 0.1). The midpoint between them, (0.6, 0.3), is equidistant from them in any p-norm. Now try a point on the perpendicular bisector. I used (0.2, 0.1). It is again equidistant in the 2-norm, but it is closer to (0.5, 0.5) when p > 2 (including p = Inf) and closer to p2 when p < 2. $\endgroup$
    – prubin
    Jun 14, 2021 at 21:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.