COMP20003 · 2020 Semester 2 · Assignment 2 · rebuilt 2026
Which business is closest? Ask a 2-d tree.
In 2020 I wrote a C program that finds the nearest of 19,117 Melbourne businesses without checking them all. The code was lost, so I rebuilt it from the test files that survived, and turned it into a map you can click to watch every comparison and every skipped block.
The assignment
A dictionary keyed on a place, not a word.
COMP20003 asked for a dictionary over the City of Melbourne's census of businesses, where the key is a location. A 2-d tree splits the map in half on longitude, then each half on latitude, and so on, so a search can rule out whole neighbourhoods at once.
01
Build
Insert 19,117 businesses, keyed on (longitude, latitude). The 4,181 distinct locations become nodes; businesses sharing an address queue on one node.
02
Stage 1 · nearest
For each query point, print every business at the closest location and count the key comparisons the search needed.
03
Experiment
Feed the same data in five orders (as published, shuffled, sorted west to east, median-first) and explain how the counts change.
How the search works
Split, descend, prune.
Split
Each node draws a line through its business: vertical at even depths, horizontal at odd ones. Everything west (or south) goes left, the rest right.
Descend
The query walks down like an insertion would, comparing itself with one node per level and remembering the closest so far.
Prune
On the way back up, a whole side is skipped when its splitting line is further away than the best answer found. That is where the savings come from.
Key results
What survived from 2020, and what the rebuild shows.
- records of 2020 output
150
The Stage 1 output saved in my 2020 testing folder (result/test1.txt, 154 lines): every business at the nearest location for 5 queries (7, 43, 1, 88, 11 per location). The rebuild reproduces it byte for byte.
- 2020 mean, sorted by x
66.2
Sorted by x was the most expensive order in 2020 too, over my 13 experiment queries. The rest don't line up with the rebuild: the Random file was cheapest (51.5) and median-first came third (59). The lost code counted differently, so only that finding carries over.
- levels deep
13 vs 66
The same 4,181 locations: balanced when inserted median-first, five times taller when inserted west to east.
- parity runs with C, in CI
40
Each run must give the C rebuild's comparison counts and a byte-identical output file, over all 10 files of the test kit. A second check rebuilds the explorer's map1 output from the web data at every location of all five orders and compares it with what the C reader reads from each file.
Five ways in
About this project
COMP20003 Algorithms and Data Structures
University of Melbourne, 2020 Semester 2. Assignment 2, individual: all code and analysis by Sunchuangyu (Rin) Huang. The original submission's test kit and my experiment numbers are preserved unchanged in the repository's coursework/ folder for reference; the assignment specification is not reproduced.
Academic integrity: this is a portfolio revival of my own past work. Please don't reuse it for a current assessment.
- Original stack (2020)
- C (gcc, make), valgrind and gdb; Python and matplotlib for the experiment plot.
- Revived stack (2026)
- C99 rebuild with tests; Next.js 16, TypeScript, Tailwind CSS, MapLibre GL with OpenFreeMap tiles, Recharts, Vitest; bootstrap statistics; optional bring-your-own-key AI with an audit log; deployed on Vercel.
- Data
- CLUE 2018 business establishments, © City of Melbourne, CC BY 4.0 (adapted: re-encoded as one compact file holding the five insertion orders of the test kit). Served as that compact derived file, not the raw CSVs.
- Credits
- Individual assignment. Built and rebuilt by Sunchuangyu (Rin) Huang.
- Source
- rNLKJA/Unimelb-undergraduate-2020-COMP20003-Assignment-2 (private GitHub repository for now; source available on request)