Locus of equidustant points

Question

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

Answer 1

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.

   

2. 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.