VoronoiMap
Estimate aggregate statistics of unknown point sets using Voronoi partitioning and nearest-neighbor oracles.
Estimate aggregate statistics of unknown point sets using Voronoi partitioning and nearest-neighbor oracles.
Click on the canvas to add points and see Voronoi regions computed in real time. Each colored cell represents the region closest to its generating point.
VoronoiMap implements the EstimateSUM algorithm: a partially informed attacker estimates aggregate statistics of an unknown point set using only a nearest-neighbor oracle.
Random points are sampled uniformly within the bounded 2D search space.
For each sample, the nearest data point is found via the nearest-neighbor oracle.
Voronoi region boundaries are approximated using binary search along perpendicular bisectors.
Region areas are computed using the Shoelace formula on the discovered vertices.
The total count is estimated from the ratio of total search area to individual cell areas.
# Clone the repository
git clone https://github.com/sauravbhattacharya001/VoronoiMap.git
cd VoronoiMap
# Install optional dependencies for O(log n) nearest-neighbor via KDTree
pip install -r requirements.txt# Basic usage: estimate count from 5-point dataset
python vormap.py datauni5.txt 5
# Multiple independent runs for better accuracy
python vormap.py datauni5.txt 5 --runs 3from vormap import get_sum, find_area, get_NN, load_data
# Estimate the number of objects in a dataset
estimated_count, max_edges, avg_edges = get_sum("datauni5.txt", 5)
# Load data for direct function calls
data = load_data("datauni5.txt")
# Find area of a single Voronoi region
area, vertices = find_area(data, 100.5, 200.3)
# Query nearest neighbor
nearest_lng, nearest_lat = get_NN(data, 500.0, 500.0)| Function | Parameters | Returns | Description |
|---|---|---|---|
get_sum(file, k) |
filename, sample count | (estimate, max_edges, avg_edges) | Core estimation algorithm. Samples k points, builds Voronoi cells, returns estimated total count. |
load_data(file) |
filename, auto_bounds=True | [(lng, lat), ...] | Load point data from file. Caches results. Auto-detects search bounds. |
find_area(data, lng, lat) |
data list, coordinates | (area, vertices) | Compute the Voronoi region area around the nearest neighbor of (lng, lat). |
get_NN(data, lng, lat) |
data list, coordinates | (lng, lat) | Find nearest neighbor. Uses KDTree (O(log n)) if scipy is available. |
set_bounds(s, n, w, e) |
south, north, west, east | None | Manually set the search space boundaries. |
| Parameter | Default | Description |
|---|---|---|
IND_S / IND_N | 0.0 / 1000.0 | South / North boundaries of the search space |
IND_W / IND_E | 0.0 / 2000.0 | West / East boundaries of the search space |
BIN_PREC | 1e-6 | Binary search precision threshold |
MAX_VERTICES | 50 | Maximum vertices per Voronoi cell before aborting |