Abstract
“The nearest station”, “the closest shop”—these are taken to be settled by the map alone. This paper shows that they are not—until a distance is chosen, “nearest” has not been defined. No new theorem or law is claimed.
First, this is the core of the paper. With the same $12$ sites, straight-line and city-block distance assign $\mathbf{12.96}$ per cent of the region to different sites (Section 2).
Second, it is not everything. $87.04$ per cent keeps the same site (Section 2).
Third, comparing a distance against itself gives exactly $\mathbf{0}$ differing cells, which tests the instrument itself (Section 2).
Fourth, Euler’s formula bounds the mean number of edges per region below $6$, giving $\mathbf{5.9880}$ for $1000$ sites (Section 3).
Fifth, however many sites are added, $6$ is never reached, and the bound does not depend on which distance is used (Section 3).
Sixth, the separator is “which site is nearest” against “how many neighbours a region has”. The first moves with the distance; the second does not (Section 4).
Scope (what is not claimed)
No new theorem or law is claimed—Voronoi diagrams, the Manhattan metric, and the bound on edges of a planar graph from Euler’s formula are all standard. No theorem is proved—Euler’s formula is used as known, and only numbers are put in. No best distance is chosen—which distance to use is decided by the application and is not the subject. Road networks are not treated—real route distance, one-way streets and waiting at lights are not the subject. The city-block metric here stands for nothing but “one distance changed”. Algorithms are not discussed—constructions such as Fortune’s sweep line are not the subject. Higher dimensions are not treated—only the plane. Degenerate cases are not treated—under the city-block metric some configurations give boundaries that are regions rather than curves; the sites here avoid that. Relation to earlier papers: Paper 182 showed that the curse of dimensionality is not one curse, and treated the collapse of nearest neighbours in high dimension—there dimension broke “nearest”; here the choice of distance does. Paper 300 showed that common root and distinct root can be decided—the two senses of “near” are distinct roots by that criterion. Paper 411 showed that a transformation preserving nothing still has an invariant—there the cross-ratio survived a change of map; here the edge bound survives a change of distance. Paper 409 showed that no undistorted map exists—here too the assumption that the map settles it fails. What is added is putting the number $12.96$ per cent on the disagreement, using a self-comparison of $0$ cells to test the instrument, giving the edge bound at three site counts, setting the distance-dependent and distance-independent quantities side by side, and placing the separator at “assignment or adjacency”.
1. Notation and the Question
Setting: Place sites $p_1,\dots,p_n$ in the plane. The region of a point $x$ is decided by the site nearest to $x$.
$$V_i=\{x: d(x,p_i)\le d(x,p_j)\ \text{for all } j\}$$Two distances are used: the straight line $\sqrt{\Delta x^2+\Delta y^2}$ and the city block $|\Delta x|+|\Delta y|$.
Observation 1.1 “Nearest” looks as if it were settled by the positions alone. Mark the points on a map and the regions follow—that is the natural thought.
Observation 1.2 But $d$ appears in the definition. Until $d$ is chosen, $V_i$ has not been defined—the positions are given; the distance is not.
Question: Change the distance, and how much changes hands.
2. 12.96 Per Cent of the Area Changes Hands
Computation 2.1: Place $12$ sites and, on a $400\times400$ grid, decide the owning site under each of the two distances.
The cells that disagree are $\mathbf{12.96}$ per cent of the whole.
Observation 2.2 This is not small. Over more than one eighth of the area, “the closest shop” becomes a different shop—the same map, the same sites, the same question.
Observation 2.3 At the same time it is not everything. $87.04$ per cent keeps the same site—in most places the answer does not change.
Observation 2.4 The instrument itself is tested. Comparing a distance against itself gives exactly $\mathbf{0}$ differing cells—that zero guarantees the disagreement is not an artefact of how the decision is made.
Observation 2.5 The disagreements are not spread evenly. They concentrate in the bands roughly equidistant from two sites—directly over a site, every distance gives the same answer.
3. And Something That Does Not Change
Computation 3.1: A Voronoi diagram is a planar graph, so Euler’s formula bounds the mean number of edges per region.
$$\bar{e}\le6-\frac{12}{n}$$| Number of sites $n$ | Bound on mean edges |
|---|---|
| $10$ | $4.8000$ |
| $100$ | $5.8800$ |
| $1000$ | $5.9880$ |
Observation 3.2 Six is never exceeded. However large $n$ is, $6-12/n<6$—$\mathbf{5.9880}$ at $1000$ sites, and still short of $6$ at a million.
Observation 3.3 The bound does not depend on the distance. Euler’s formula uses only that the figure can be drawn in the plane—and under either distance it can.
Observation 3.4 So “who is my neighbour” changes with the distance, while “how many neighbours at most” does not. Two layers of the same figure—one geometric, one topological.
Observation 3.5 Six is the number of the honeycomb. Because the mean tends to $6$, and regular hexagons tile the plane—which does not make the individual regions hexagons.
4. The Separator
The separator: which site is nearest, or how many neighbours a region has.
Observation 4.1 The first changes with the distance. $12.96$ per cent of the area changes hands—because it is a geometric quantity.
Observation 4.2 The second does not. The bound stays $6-12/n$—because it is a topological quantity.
Observation 4.3 These are distinct roots by the criterion of Paper 300. Both are called properties of the Voronoi diagram, but they depend on different things—one on the distance function, one on planarity.
Observation 4.4 So “I drew the Voronoi diagram” is not enough. Without saying under which distance, $12.96$ per cent of the figure is undetermined—giving the positions does not suffice.
Observation 4.5 To be honest—the value $12.96$ per cent depends on the arrangement of the sites. A different set of $12$ gives a different number—what does not move is that it is not zero. The two distances agree everywhere only when the sites are specially arranged.
Observation 4.6 One last thing—calling the city-block metric “close to real roads” would be saying too much. This paper does not claim it—it was used to see what happens when one distance is changed.
5. Roll Call and Closing
- $12.96$ % changes hands (Computation 2.1): with the same sites.
- $87.04$ % does not (Observation 2.3): not everything.
- $0$ cells differ under self-comparison (Observation 2.4): the instrument checked.
- Disagreements concentrate in the equidistant bands (Observation 2.5): same answer over a site.
- Bound $4.8000$ at $n=10$ (Computation 3.1): from Euler.
- $5.8800$ at $n=100$ (Computation 3.1): approaching $6$.
- $5.9880$ at $n=1000$ (Computation 3.1): still under $6$.
- The bound is distance-independent (Observation 3.3): only planarity is used.
- Geometry moves, topology does not (Observation 3.4): two layers of one figure.
- The separator is assignment or adjacency (Observation 4.3): distinct roots by Paper 300.
Closing: “The nearest station”, “the closest shop”—these are taken to be settled by marking points on a map—but the definition of the region contains a distance $d$, and until $d$ is chosen “nearest” has not been defined. The positions are given; the distance is not. And changing the distance really does change the answer—deciding the owning site for the same $12$ sites on a $400\times400$ grid, the cells that disagree between straight-line and city-block distance are $\mathbf{12.96}$ per cent of the whole. Over more than one eighth of the area “the closest shop” becomes a different shop, with the same map, the same sites and the same question. At the same time it is not everything: $\mathbf{87.04}$ per cent keeps the same site, and the disagreements concentrate in the bands roughly equidistant from two sites. That the disagreement is not an artefact of the decision procedure is guaranteed by comparing a distance against itself, which gives exactly $\mathbf{0}$ differing cells. And something survives the change—a Voronoi diagram is a planar graph, so Euler’s formula bounds the mean number of edges per region by $6-12/n$, giving $\mathbf{4.8000}$ at $n=10$, $\mathbf{5.8800}$ at $n=100$ and $\mathbf{5.9880}$ at $n=1000$. However many sites are added, $6$ is never reached, and since the formula uses only that the figure can be drawn in the plane, the bound does not depend on the distance. Six is the number of the honeycomb, because regular hexagons tile the plane—which does not make the individual regions hexagons. One thing separates them—which site is nearest, or how many neighbours a region has. The first is geometric and moves with the distance; the second is topological and does not. They are distinct roots by the criterion of Paper 300, depending respectively on the distance function and on planarity. So “I drew the Voronoi diagram” is not enough: without saying under which distance, $12.96$ per cent of the figure is undetermined. To be honest—the value $12.96$ per cent depends on the arrangement, and a different set of $12$ gives a different number. What does not move is that it is not zero; the two distances agree everywhere only when the sites are specially arranged. One last thing—calling the city-block metric “close to real roads” would be saying too much, and this paper does not claim it. It was used to see what happens when one distance is changed.
References
- Dirichlet, G. L. (1850). Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die reine und angewandte Mathematik.
- Voronoi, G. (1908). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal für die reine und angewandte Mathematik.
- Okabe, A., Boots, B., Sugihara, K., & Chiu, S. N. (2000). Spatial Tessellations (2nd ed.). Chichester: Wiley.
- Aurenhammer, F. (1991). Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys.
- Yamagishi, Y. (2026). “The Curse of Dimensionality” Is Not One Curse [Paper 182]. Zenodo. 10.5281/zenodo.22104170
- Yamagishi, Y. (2026). The Three Hundredth Census: Whether Two Things Share a Root Is Decidable [Paper 300]. Zenodo. 10.5281/zenodo.22171914
- Yamagishi, Y. (2026). There Is No Undistorted Map, and the Projection Is Not to Blame [Paper 409]. Zenodo. 10.5281/zenodo.22699616
- Yamagishi, Y. (2026). A Transformation That Preserves Nothing Still Has an Invariant [Paper 411]. Zenodo. 10.5281/zenodo.22699656
Reference
Yamagishi, Y. (2026). “Nearest” Is Not Defined Until the Distance Is [Paper 412]. YOI: https://www.yamagishiyuuki.com/yoi/412
DOI: 10.5281/zenodo.22699661
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 412. This paper is a preprint and has not been peer reviewed.