Higher-Order Voronoi Diagrams for k-Nearest Neighbor Queries

A Python implementation and study of k-th order Voronoi diagrams as a spatial index for accelerating k-nearest neighbor (k-NN) queries, developed for the Computational Geometry course at Bilkent University (MSc Computer Engineering).

What this project does

Given a set of generator points in the plane, a k-th order Voronoi diagram partitions the plane into cells where every point in a single cell shares the same set of k nearest generators. This means a k-NN query reduces to a single point-location query — once the diagram is built, lookups are sub-linear in the number of generators.

This repository contains:

• A from-scratch class-based Voronoi implementation (Point, VoronoiRegion, VoronoiDiagram) built on top of Delaunay triangulation (voronoi.py).
• A SciPy-backed reference implementation for validation (main.py, geometry.py).
• An interactive matplotlib app (voronoi_app.py) where you click to add generator points and adjust k via a text box; the k-th order diagram redraws live using a KDTree.
• Empirical timing measurements comparing brute-force k-NN against KDTree-accelerated k-NN over varying input sizes (k_nearest_query.ipynb).
• The full project report and presentation slides.

Files

File	What it is
voronoi.py	Class-based Voronoi diagram (Point, VoronoiRegion, VoronoiDiagram)
voronoi_app.py	Interactive k-th order Voronoi GUI (click to add points, text box to set k)
geometry.py, Point.py, Plane.py	Geometry primitives
main.py	SciPy-backed Voronoi + brute-force k-NN reference
main.ipynb	Construction walkthrough with figures
k_nearest_query.ipynb	k-NN timing experiments
Computation_Geometry_Project_Final_Report.pdf	Full report
K-NN Queries Using Higher-Order Voronoi Diagrams.pptx	Final presentation
*.png	Figures used in the report and slides

Running it

pip install numpy scipy matplotlib
python voronoi_app.py

Left-click anywhere in the plot window to add generator points. Enter a value for k in the text box (top-right) to redraw as a k-th order diagram.

Selected figures

voronoi_k_1.png, voronoi_k_2.png, voronoi_k_3.png, voronoi_k_4.png show the same generator set rendered at increasing orders. time_ranges.png shows the empirical query-time advantage of the indexed approach over brute force as n grows.

Stack

Python · NumPy · SciPy (Voronoi, Delaunay, KDTree) · Matplotlib

Course

CS 567 — Computational Geometry, Bilkent University.