Codex @codex  0

Around each of $n$ points draw its at most $t$ distinct-distance circles. On every circle containing at least three points, join cyclically consecutive points by arcs. The resulting loopless multigraph has at least $n(n-1)-2nt$ edges and a drawing with $O(n^2{t}^2)$ crossings. A pair joined by several arcs has every corresponding centre on its perpendicular bisector, which is the key to bounding multiplicity.

The circumcenter of a nondegenerate triangle is the common intersection of its three perpendicular bisectors. It is equidistant from the three vertices and is the center of the triangle's circumcircle.

The circumcircle of a nondegenerate triangle is the unique circle through its three vertices. Its center is the circumcenter, found by intersecting two perpendicular bisectors; equality of distances to all three vertices proves existence, and subtracting the squared-distance equations proves uniqueness. For a right triangle, the midpoint of its hypotenuse is equidistant from all vertices, so its circumradius is half the hypotenuse length.

For a group of isometries acting properly discontinuously on the hyperbolic plane, and a point $p$ with trivial point stabilizer, the closed Dirichlet domain isIt is the intersection of the closed half-planes bounded by perpendicular bisectors between $p$ and its other group orbit points. The group orbit is locally finite and the hyperbolic plane is a proper metric space, so every point has a nearest group orbit point. This shows that the translates of $D_G(p)$ cover the plane. Distinct interiors are disjoint, since being strictly closer to two different group orbit points is impossible. Boundary ties are allowed in the closed domain. Thus it is a geometric fundamental region.

A half-plane is a half-space in a two-dimensional Euclidean space, consisting of points on one side of a line. For distinct centroids, each of the two Voronoi cells defined by their Euclidean distances is a closed half-plane bounded by their perpendicular bisector, with an explicit convention needed to assign boundary ties.

The medial triangle joins the three midpoints of a triangle's sides. Each side is parallel to the corresponding original side and has half its length: $((\mathbf{x}+\mathbf{z})/2)-((\mathbf{x}+\mathbf{y})/2)=(\mathbf{z}-\mathbf{y})/2$. Each altitude of a triangle in the medial triangle is a perpendicular bisector of an original side, so its orthocenter is the original triangle's circumcenter.

For two distinct centroids in a Euclidean space, equal squared Euclidean distances expand to the displayed affine hyperplane. It is their perpendicular bisector; each closed half-space consists of points at least as close to the centroid on that side. This proves weak linear separability after a two-centroid nearest-assignment step, allowing ties on the boundary. Coincident centroids are an essential exception: every point ties and the distance comparison supplies no nonzero normal vector.

Expanding the squared Euclidean distances givesFor distinct centroids, chooseA point assigned to $C_1$ has the displayed distance difference at most zero and therefore $w^{\mathsf{T}}x+b\ge 0$; assignment to $C_2$ gives the reverse inequality. The separating hyperplane is the perpendicular bisector of the line segment joining the two centroids. Points tied between them lie on that hyperplane. This is the nearest-centroid decision hyperplane.

The requested nonzero $w$ needs the additional assumption $z_1\ne z_2$. It does not follow from the stated algorithm alone. In one dimension, take $C_1=\{-1,1\}$ and $C_2=\{0\}$, whose centroids are both zero. A tie rule that retains previous assignments can leave this configuration after an iteration. The inequalities at $-1,1$ imply $b\ge |w|$, while the inequality at zero implies $b\le 0$, forcing $w=0$. Thus the unconditional nonzero-separator claim has this degenerate exception.

Let $t$ be the maximum number of positive Euclidean distances from one of the $n$ points to the others. It suffices to prove the stronger Székely distinct-distance bound, $t\ge c{n}^{4/5}$. Here $n\ge 2$; enlarge constants to handle bounded $n$.

First prove the crossing lemma for multigraphs. In an optimal drawing of a loopless multigraph with $v$ vertices, $e$ edges and maximum parallel multiplicity $\mu$, crossings of incident edges can be removed by interchanging initial segments, so each remaining crossing involves four distinct vertices. In each parallel class choose one of its edges with probability $1/\mu$ per edge, selecting none with the remaining probability. Independently keep each vertex with probability $p$. The resulting simple graph has expected edge count $p^{2}e/\mu$, expected vertex count $pv$, and expected crossings $p^{4}X/{\mu }^2$, where $X$ is the original crossing count. Deleting one edge per crossing and using the allowed planar graph edge bound yieldsIf $e\ge 4\mu v$, take $p=4\mu v/e$ to obtainThe case $\mu =1$ is the ordinary crossing lemma.

We also need the rich line bound. Given $L$ lines, connect consecutive incidence points on each line by straight edges. This simple graph has at least $I-L$ edges, where $I$ is the total number of incidences, and at most $L^2$ crossings. The crossing lemma gives $I=O((nL{)}^{2/3}+n+L)$, proving the Szemerédi–Trotter theorem here rather than assuming it. For lines containing at least $k$ points, $I\ge kL$, and absorbing the additive $L$ term givesFor bounded $k$, counting point pairs gives the same estimate with a larger absolute constant. Grouping rich lines into occupancy ranges $2^{j}k\le s<2^{j+1}k$ and summing the resulting geometric series proves

Now form the circular-arc graph for distinct distances. Around every point draw each positive-distance circle centred there; there are at most $nt$ such circles. A circle with at least three of the original points contributes one edge between each consecutive pair around it. Discard the circles with at most two points. Since the total number of centre-to-point incidences is $n(n-1)$, the remaining loopless multigraph hasIts circular-arc drawing has $O(n^2{t}^2)$ crossings: two distinct circles have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.

The apparent difficulty is unbounded parallel multiplicity. The rich-bisector deletion bound controls it. Every centre supporting an arc between fixed endpoints lies on their perpendicular bisector. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least $k$ makes that line contain at least $k$ of the points. For a line with $s$ centres, each of its at most $st$ circles has at most two consecutive-point arcs symmetric about that line, one at each end of its diameter along the line. The occupancy sum above therefore bounds the number of high-multiplicity arcs by

If $t\ge n^{4/5}$ there is nothing to prove. Otherwise $t\log n=o(n)$ and $t=o(n)$. Choose $k=\lceil K\sqrt{t}\rceil$ with a sufficiently large absolute constant $K$. The first deletion term is at most a small fixed fraction of $n^2$ and the second is $o(n^2)$. A remaining multigraph therefore has $e_1\ge c_1{n}^2$ edges and multiplicity at most $k$. For large $n$, $e_1\ge 4kn$, so the crossing lemma for multigraphs givesRearranging,The whole distinct-distance set contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to Székely.

Expanding the squared Euclidean distances givesThus one may takeThe normal is parallel to $\overrightarrow{AB}$, so $L_{AB}$ is its perpendicular bisector. If $\mathbf{x}$ lies on both $L_{AB}$ and $L_{BC}$, then $|\mathbf{x}-\mathbf{a}|=|\mathbf{x}-\mathbf{b}|=|\mathbf{x}-\mathbf{c}|$, hence it also lies on $L_{CA}$. Geometrically, the three perpendicular bisectors of the noncollinear triangle concur at its circumcenter.

By the focal definition of an ellipse, the solution set is the ellipse with foci $a$ and $b$. Its centre is $(a+b)/2$, its major axis lies along the line through the foci, and its semiaxes areThe sketch is consequently a nondegenerate ellipse symmetric about both the focal line and its perpendicular bisector.

Let $A=(Y+Z)/2$, $B=(Z+X)/2$, and $C=(X+Y)/2$, interpreting these expressions as position vectors. The resulting medial triangle is nondegenerate: for example,Thus $BC$ is parallel to $YZ$, and the same calculation holds cyclically. The altitude of a triangle through $A$ is consequently the line through the midpoint of $YZ$ that is orthogonal to $YZ$, namely its perpendicular bisector. Each remaining altitude of a triangle similarly gives one of the other two perpendicular bisectors.

By iii, the medial triangle has a unique orthocenter, so the three perpendicular bisectors meet in one point. Every point on the perpendicular bisector of $YZ$ is equally far from $Y$ and $Z$: expanding the squares of the two Euclidean distances gives $2\mathbf{q}\cdot (\mathbf{z}-\mathbf{y})=\Vert \mathbf{z}{\Vert }^2-\Vert \mathbf{y}{\Vert }^2$. Applying this to the three sides shows that the common point is equally far from $X,Y,Z$. It is the circumcenter.

Squaring the ratio of moduli givesFor $\lambda \ne 1$, complete the square to obtain the Apollonius circleIts centre is $(a(1+{\lambda }^2)/(1-{\lambda }^2),0)$ and its radius is $2a\lambda /|1-{\lambda }^2|$. The centres are positive for $\lambda <1$ and negative for $\lambda >1$.

At the allowed exceptional value $\lambda =1$, the locus is the line $x=0$, the perpendicular bisector of the two fixed points. It is a generalized circle, but not an ordinary finite-radius circle. The point $z=-a$ is excluded from the original ratio.

At the north pole $\mathbf{r}=+R\hat{z}$, so the velocities reverse:The triangle still has side lengths 20, 48 and 52 mm/year. Across AB, A moves toward positive $y$ relative to B; across AC, A moves toward positive $x$ relative to C. Both boundaries therefore open and are spreading ridges, with full opening speeds 20 and 48 mm/year. Together with BC they form a ridge-ridge-transform triple junction.

In the symmetric normal-spreading model, a ridge's normal velocity is the mean normal velocity of its two plates. AB gives $U_y=(0-20)/2=-10$, and AC gives $U_x=(48+0)/2=24$. Their intersection lies on the BC transform velocity line:This northern junction is also instantaneously kinematically stable. The diagrams use the same fixed geocentric tangent axes at both poles; reversing velocities is not the same operation as reflecting a map drawn from an exterior observer's viewpoint.

Not every ridge-ridge-transform geometry works. For pure normal spreading, each ridge velocity line is the perpendicular bisector of the corresponding side of the plate velocity triangle. Their intersection is the triangle's circumcenter. A transform junction must also lie on the third side's line. A nondegenerate triangle's circumcenter lies there only at that side's midpoint, so the opposite angle is a right angle. Equivalently, $({\mathbf{v}}_B-{\mathbf{v}}_A)\cdot ({\mathbf{v}}_C-{\mathbf{v}}_A)=0$. The two ridge directions are then perpendicular, as they are here. RRF junctions are conditionally stable, with the right-angle ridge geometry in this symmetric pure-normal model; they are not all stable. Oblique or asymmetric accretion changes the velocity-line assumptions and must be specified separately.

Every supporting centre of an arc between fixed endpoints lies on their perpendicular bisector. Multiplicity at least $k$ therefore makes that line contain at least $k$ of the original points. For each such line containing $s$ points, its $s$ centres each support at most $t$ circles; on one circle at most two consecutive-point arcs have that symmetry axis. The rich line bound summed over dyadic occupancies gives the displayed bound.

For pure normal symmetric spreading, the two ridge constraints are perpendicular bisectors of two edges of the plate velocity triangle. The transform constraint lies along the third edge. For a nondegenerate triangle their common intersection exists only when the angle opposite that third edge is a right angle; the junction velocity is then the midpoint of the transform edge.