5

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?

bajun65537
  • 231
  • 2
  • 4
  • 1
    You can use scipy for $L_2$. – Kuifje Jun 13 '21 at 08:58
  • Yes. But what about other metrics? Are they that little researched? – bajun65537 Jun 13 '21 at 14:05
  • 1
    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. – Kuifje Jun 13 '21 at 14:13
  • 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. https://gis.stackexchange.com/a/373761/751. – Andy W Jun 13 '21 at 15:57
  • @AndyW The $L$ notation refers to the metric (distance measure) being used. $L_2$ is euclidean distance (square root of the sum of squared differences). $L_1$ is the sum of the absolute differences. More generally, $L_p$ is the norm $\parallel x-y\parallel_{p}=\sqrt[p]{\sum_{i}(x_{i}-y_{i})^{p}}.$ – prubin Jun 13 '21 at 18:11
  • I am just still confused how exactly the L norms are relevant in this example. Here is an example in R I cooked up @prubin showing two points. Norms 2 to 5 all produce the same results (not sure if this generalizes all the time, would like to see a counter example though if it exists!), and L1 is undetermined for some areas. Most examples I am familiar with in GIS take either a function of the Euclidean distance, or the input points are weighted, see again here. – Andy W Jun 13 '21 at 21:19
  • Although this code is for clustering, you might be able to use it for your problem. https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html – Amin Jun 14 '21 at 04:11
  • @AndyW I guess it makes sense that there is no big difference between metrics 2,3,4,5 as they are relatively similar. The cases that are most interesting (as they do differ) are L1 (think of it as a distance in a city center where the roads make a grid - to get from one point to the other you need to go three blocks west and one block north), L2 (Euclidean distance as if you wanted to go from one point to the other on a football field and thus can walk straight) and finally, as you increase p you'll also be able to consider L-inf norm whose Voronoi diagram should also be quite different. – bajun65537 Jun 14 '21 at 08:07
  • 2
    @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. – prubin Jun 14 '21 at 21:31

0 Answers0