L1 Metric Voronoi diagrams

[Harry de Beuker]

Hello everyone,

I was wondering what the upper bound of a 2-dimensional L1 Metric (Manhattan distance) Voronoi diagram would be. The lower bound is obviously the same as an L2 metric Voronoi diagram, namely zero.

I was considering using Euler's formula but I do not know how the handle the different faces that occur using L1 Metric.

I was considering the upper bound to be 4n - 6, since all possible Voronoi diagrams I could add at most 4 vertices for each point added.

Thanks in advance.

-- Harry

[Nicolas Bonneel]

Post by Harry de Beuker
Hello everyone,
I was wondering what the upper bound of a 2-dimensional L1 Metric (Manhattan distance) Voronoi diagram would be. The lower bound is obviously the same as an L2 metric Voronoi diagram, namely zero.
I was considering using Euler's formula but I do not know how the handle the different faces that occur using L1 Metric.
I was considering the upper bound to be 4n - 6, since all possible Voronoi diagrams I could add at most 4 vertices for each point added.

An upper bound on what and over what ?
An upper bound on the maximum number of facets over all possibles sets
of vertices of given cardinality ?
An upper bound on the cost over all possible sets of vertices of any
cardinality ? (unbounded : take points arbitrarily far away).
An upper bound on the number of edges over all possibles Voronoi
diagrams for a given set of points ? (well, the Voronoi diagram is
unique... but nobody prevents me from maximizing over a set of
cardinality 1)
An upper bound on the number of vertices created by intersecting facets,
over I don't know what ?...

.....