I have problem which involves finding the vornoi diagram of n points in the $\mathrm{R}^2$ plane with distance metric as
1.) the $L_1$ i.e is distace between two points is $d(A,B)=|A_x-B_x|+|A_y-B_y|$
I guess that locus of equdistant point in $L_1$ norm is same as that of $L_2$ which is the perpendicular bisector and hence the vornoi structure won't change in this case.
2.) using $L_{\infty}$ with $d(A,B)=max(|A_x-B_x|,|A_y-B_y|)$
I'm unable to figure out how will the locus of points equidistant from two points using this distance metric look like
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
You guessed wrong: the equidistant locus is piecewise linear and will in general consist of three distinct pieces, one diagonal and two horizontal or vertical.
Again you get three linear pieces, but now two are diagonal and one is horizontal or vertical.
The word “diagonal” in the above refers to a line of slope $\pm1$.
See also Plot VoronoiDiagram with different Norms on Stack Overflow about how to plot such diagrams with Mathematica, and this paper on a CGAL implementation of $L_\infty$ norm Voronoi diagrams for large scale applications.
-
1$\begingroup$ Thank you, can you explain why is it behaving like this. All points in perpendicular bisector have the same manhattan distance from both points, then why is it not the locus ? Can you also give some clue on how the locus will be in L infinity ? $\endgroup$– LearnerCommented May 6, 2015 at 8:54