Skip to content
K-d Tree Explorer, home
All decision records

DR-002Accepteddecided 2026-10-09

Handle ties the way the evidence allows, and match the 2020 output byte for byte

docs/decisions/DR-002-tie-handling-and-output-format.md

Context

A 2-d tree meets ties in three places: a new key equal to a node's key on the split axis, two businesses at exactly the same location, and two different locations at exactly the same distance from a query. Each needs a rule, and the rule changes either the tree, the answer, the comparison count or the printed output. The output format matters too, because result/test1.txt is the one 2020 output that survived (DR-001), and a byte-for-byte match is the strongest test I have.

Decision

Settle each tie with the simplest rule that the saved output allows, and reproduce that output's format byte for byte.

  • Equal key on the split axis: strictly smaller goes left, equal or greater goes right, at insertion and during search.
  • Same location: one node per (x, y), holding its businesses in the order of the file being read. Every reordered file therefore prints its businesses in its own order.
  • Equal distances: the nearest search keeps the first location found (it replaces the best only when a distance is strictly smaller), and it crosses to the far side of a split only when the split line is strictly closer than the best distance so far. The radius search is inclusive: a location exactly r away is inside, and the far side is searched when the split line is at most r away.
  • Output: <query as typed> --> Field: value || … || per business, LF line endings, quotes removed from quoted fields, a blank line between queries, and NOTFOUND when a radius search finds nothing. Standard output gets one <query> --> <comparisons> line per query. Query lines that do not hold exactly two numbers (three for Stage 2) are skipped and reported on standard error.

Options considered

  1. Equal keys left (<= goes left). Rejected. With the kit's median-first file, the strict rule keeps the tree perfectly balanced, and it is the convention the course used.
  2. One node per business. Rejected. result/test1.txt prints all businesses at a location together for one query, which one node per location gives directly. One node per business also changes the comparison counts.
  3. Equal distances: keep the last location found, or break ties by id. Rejected. Nothing in the evidence decides it, and keeping the first found is the plain reading of "nearest so far".
  4. A tidier output format (JSON, or one line per location). Rejected for the program itself. The site shows the structured result next to the exact map1/map2 output instead.

Why

Each rule either reproduces a byte of the surviving output or is the simplest rule consistent with it. Matching bytes exactly is a test that anyone can run, which an approximate match is not.

What happened

  • make test regenerates result/test1.txt byte for byte (154 lines, 57,807 bytes), and the web app's output matches the C programs for all five insertion orders (40 of 40 output files in the parity fixture).
  • The strict rule keeps the median-first tree at 13 levels. In that file's full-precision keys only 48 of the 4,181 locations share an x value with another location, so the evidence for the equal-goes-right rule is thin. (The original file's 5-decimal keys tie far more often: 2,402 locations share an x value.) The balanced build in DR-003 shows a cost of the rule: tied keys can make a subtree one level deeper.
  • No exact distance tie between two different locations occurs for any of the 218 Stage 1 test queries on any of the five files (checked by brute force in web/src/lib/rebuild-evidence.test.ts), so the first-found rule is untested by the evidence. A unit test pins it instead.
  • The comparison counts these rules produce do not match the 2020 counts (DR-001). Tie handling is not the cause: I tried both strict and non-strict tests at every step.

What I'd change

Print the comparison rule next to every count in the program's own output (for example --> 14 node comparisons), so a future reader of a saved output knows what was counted. I would also report an exact distance tie when it happens, rather than settle it silently.