Why use the square-root trick for sampling a uniform random point inside a circle?

Naively sampling r = R * U (linear in U) concentrates points near the centre because the annular area at radius r is proportional to r, not U. The square-root transform r = R * sqrt(U) maps U uniformly over the circle's area, so the displaced POI has equal probability of landing anywhere inside the fuzzing boundary — a requirement for differential privacy Laplace-mechanism equivalence.

Configuring Spatial Fuzzing Radius for Sensitive POIs

Q: How does the density-adjusted radius formula behave at the urban–rural boundary?

At the boundary where local_density drops below target_density, the sqrt ratio exceeds 1.0, expanding the effective radius automatically. The sqrt (rather than linear) scaling prevents over-expansion in extremely sparse areas: a 10× density drop yields only a 3.16× radius increase, keeping the fuzzed point within a geographically plausible region rather than displacing it across administrative boundaries.

Q: Can the same radius configuration satisfy both k-anonymity and differential privacy simultaneously?

Yes, with careful parameter alignment. Set the base radius R = Δ / ε where Δ is the L1 sensitivity of the location query and ε is your privacy budget. Then verify that the resulting circular displacement zone contains at least k distinct records. If the k-anonymity check fails (too sparse), increase R or fall back to administrative-boundary aggregation. The two models complement rather than conflict — DP governs the displacement distribution shape; k-anonymity governs the minimum population in the landing zone.

The effective fuzzing radius for a sensitive point of interest is determined by its sensitivity tier, the local population density, and the minimum displacement required to satisfy a target k-anonymity threshold — a fixed, uniform radius fails because it simultaneously over-masks dense urban clusters and under-masks isolated rural locations.

Core Calculation and Parameter Table permalink

The density-adjusted effective radius is:

r_{\text{eff}} = r_{\text{base}} \times \sqrt{\frac{\rho_{\text{target}}}{\rho_{\text{local}}}}

where $r_{\text{base}}$ is the tier baseline in metres, $\rho_{\text{target}}$ is the reference point density (points per km²) chosen at calibration time, and $\rho_{\text{local}}$ is the kernel-density estimate at the POI location.

The square-root transform keeps radius growth sub-linear as density falls, preventing extreme displacements in sparse zones while still expanding the buffer enough to absorb additional re-identification risk.

Sensitivity Tier Baseline Radii permalink

Tier	Example POI types	$r_{\text{base}}$ (urban)	$r_{\text{base}}$ (rural)	Minimum $k$
`critical`	Domestic-violence shelters, paediatric psychiatric units, witness-protection sites	1200 m	2000 m	10
`high`	Law enforcement substations, critical-infrastructure nodes, border checkpoints	600 m	1200 m	7
`medium`	Community health clinics, educational facilities, addiction treatment centres	200 m	500 m	5
`low`	Public parks, retail transit stops, open government offices	50 m	150 m	3

Worked Numeric Example permalink

A domestic-violence shelter (critical) in a district where $\rho_{\text{local}} = 0.25\ \text{pts/km}^2$ and $\rho_{\text{target}} = 1.0\ \text{pts/km}^2$ :

r_{\text{eff}} = 1200 \times \sqrt{\frac{1.0}{0.25}} = 1200 \times 2 = 2400\ \text{m}

The 2400 m radius is then clamped to the regulatory ceiling (3000 m in most jurisdictions) and a k-check verifies ≥ 10 records exist within a 2400 m circle centred on the displaced point.

Python Implementation permalink

The function below handles CRS projection, per-tier radius lookup, density-adjusted scaling, and uniform circular displacement. It returns the dataset in its original CRS for downstream compatibility with spatial fuzzing and buffer zone workflows.

import geopandas as gpd
import numpy as np
from shapely.geometry import Point


def configure_fuzzing_radius(
    gdf: gpd.GeoDataFrame,
    tier_radii: dict[str, float],
    density_col: str = "local_density",
    target_density: float = 1.0,
    metric_crs: str = "EPSG:3857",
    seed: int = 42,
) -> gpd.GeoDataFrame:
    """
    Apply density-adjusted spatial fuzzing to a GeoDataFrame of sensitive POIs.

    Args:
        gdf: GeoDataFrame with a 'tier' column and a defined CRS.
             Optionally includes a local_density column (points per km²).
        tier_radii: Base radius (metres) per tier, e.g.
                    {"critical": 1500.0, "high": 800.0,
                     "medium": 350.0, "low": 100.0}.
        density_col: Column holding kernel-density estimates.
                     If absent, density scaling is skipped.
        target_density: Reference density for the scaling formula
                        (same units as density_col). Typically the
                        median density across the study area.
        metric_crs: Projected CRS for metre-accurate buffer math.
                    Use a local UTM zone for highest precision,
                    or EPSG:3857 for global web-mapping pipelines.
        seed: RNG seed for reproducible audit trails.

    Returns:
        GeoDataFrame with displaced geometries in the original CRS.
        Adds 'base_radius' and 'effective_radius' columns for audit logging.

    Raises:
        ValueError: If input CRS is undefined or a tier is unmapped.
    """
    if not gdf.crs:
        raise ValueError(
            "Input GeoDataFrame must have a defined CRS. "
            "Call gdf.set_crs('EPSG:4326') or equivalent first."
        )

    rng = np.random.default_rng(seed)
    original_crs = gdf.crs

    # --- 1. Project to a metric CRS for distortion-free radius arithmetic ---
    # Degree-based buffers in EPSG:4326 are latitude-dependent and will
    # silently invalidate radius guarantees at mid/high latitudes.
    gdf_proj = gdf.to_crs(metric_crs).copy()

    # --- 2. Look up the base radius for each POI's sensitivity tier ---
    if "tier" not in gdf_proj.columns:
        raise KeyError("Missing 'tier' column; add it before calling this function.")

    gdf_proj["base_radius"] = gdf_proj["tier"].map(tier_radii)
    missing_tiers = gdf_proj.loc[gdf_proj["base_radius"].isna(), "tier"].unique()
    if len(missing_tiers):
        raise ValueError(f"No radius mapping for tiers: {missing_tiers.tolist()}")

    # --- 3. Density-adjusted scaling: r_eff = r_base × sqrt(ρ_target / ρ_local) ---
    # sqrt keeps growth sub-linear so sparse-area radii stay geographically sensible.
    if density_col in gdf_proj.columns:
        # Clip to a small positive floor to avoid division by zero in unpopulated zones.
        density_ratio = target_density / gdf_proj[density_col].clip(lower=1e-6)
        gdf_proj["effective_radius"] = gdf_proj["base_radius"] * np.sqrt(density_ratio)
    else:
        gdf_proj["effective_radius"] = gdf_proj["base_radius"]

    # --- 4. Uniform circular displacement via the square-root sampling trick ---
    # r = R * sqrt(U) maps U∈[0,1] uniformly over the disc area, preventing
    # the centre-concentration bias of the naive r = R * U approach.
    u = rng.random(len(gdf_proj))
    v = rng.random(len(gdf_proj))

    r_vals = gdf_proj["effective_radius"].values
    theta = 2.0 * np.pi * v
    r_disp = r_vals * np.sqrt(u)  # uniform-area sampling

    dx = r_disp * np.cos(theta)
    dy = r_disp * np.sin(theta)

    # --- 5. Rebuild geometries with the displacement applied ---
    # Vectorised coordinate arithmetic avoids a slow Python-level loop.
    new_x = gdf_proj.geometry.x + dx
    new_y = gdf_proj.geometry.y + dy
    gdf_proj["geometry"] = gpd.points_from_xy(new_x, new_y)
    gdf_proj = gdf_proj.set_crs(metric_crs, allow_override=True)

    # --- 6. Return to the original CRS for downstream compatibility ---
    return gdf_proj.to_crs(original_crs)


# --- Usage ---
# tier_map = {
#     "critical": 1500.0,
#     "high":     800.0,
#     "medium":   350.0,
#     "low":      100.0,
# }
# fuzzed = configure_fuzzing_radius(poi_gdf, tier_map, target_density=1.5)
# fuzzed[["tier", "base_radius", "effective_radius", "geometry"]].to_file("fuzzed.gpkg")

Verification Snippet permalink

Run this after applying fuzzing to confirm the displacement distribution and k-anonymity compliance before publishing:

import numpy as np
from scipy.spatial import cKDTree


def verify_fuzzing(
    original: gpd.GeoDataFrame,
    fuzzed: gpd.GeoDataFrame,
    tier_radii: dict[str, float],
    k_min: int = 5,
    metric_crs: str = "EPSG:3857",
) -> dict:
    """
    Checks that:
      1. Every displaced point lies within its declared effective_radius.
      2. Each displaced point has at least k_min neighbours within effective_radius.

    Returns a dict with pass/fail flags and violation counts.
    """
    orig_m = original.to_crs(metric_crs)
    fuzz_m = fuzzed.to_crs(metric_crs)

    orig_xy = np.column_stack([orig_m.geometry.x, orig_m.geometry.y])
    fuzz_xy = np.column_stack([fuzz_m.geometry.x, fuzz_m.geometry.y])
    displacements = np.linalg.norm(fuzz_xy - orig_xy, axis=1)

    # Check 1: displacement does not exceed effective_radius
    r_eff = fuzz_m["effective_radius"].values
    radius_violations = int((displacements > r_eff).sum())

    # Check 2: k-anonymity — at least k_min fuzzed neighbours within r_eff
    tree = cKDTree(fuzz_xy)
    neighbour_counts = np.array([
        len(tree.query_ball_point(pt, r)) - 1  # exclude self
        for pt, r in zip(fuzz_xy, r_eff)
    ])
    k_violations = int((neighbour_counts < k_min).sum())

    return {
        "radius_violations": radius_violations,
        "k_violations": k_violations,
        "max_displacement_m": float(displacements.max()),
        "median_displacement_m": float(np.median(displacements)),
        "pass": radius_violations == 0 and k_violations == 0,
    }

# report = verify_fuzzing(poi_gdf, fuzzed, tier_map, k_min=5)
# assert report["pass"], f"Fuzzing verification failed: {report}"

A passing result requires radius_violations == 0 and k_violations == 0. If either count is non-zero, tighten the base radius or fall back to administrative-boundary aggregation before publication.

Edge Cases and Adjustments permalink

Sparse rural zones. When local_density approaches zero, effective_radius grows without bound. Clamp effective_radius to a regulatory ceiling (typically 3000 m) and log a warning for manual review. Points that still fail the k-check after clamping must be aggregated to the nearest census tract or postal zone — never published at point granularity.
Non-uniform density zones (urban–rural boundaries). If a POI sits at a density discontinuity — for example, a clinic on the edge of an industrial district — compute local_density using a fixed 5 km KDE search radius rather than an administrative-boundary average to avoid abrupt radius jumps across the zone edge.
Temporal windowing. When the underlying population data is time-stratified (e.g., night-time vs. daytime population grids), recalculate local_density per time window. A healthcare facility that is densely surrounded during business hours may be effectively isolated at night; the nightly effective_radius should be scaled accordingly. This matters for any dataset that will be joined with coordinate jittering noise injection applied at different temporal resolutions.
CRS boundary crossings. A UTM zone boundary bisecting the study area can cause displacement vectors to cross into an adjacent zone, producing metre-scale distortions if the metric CRS is not re-evaluated. Either use EPSG:3857 for full-coverage consistency, or clip the dataset by UTM zone and process each zone separately with its own metric_crs.

Frequently Asked Questions permalink

What fuzzing radius satisfies GDPR pseudonymisation requirements for healthcare POIs?

GDPR does not mandate a specific radius, but Recital 26 requires that re-identification be infeasible using “all means reasonably likely”. For healthcare POIs, the operational baseline is 500 m minimum in dense urban zones and 1200 m in rural areas, combined with a k-anonymity check of k ≥ 5 within the displaced zone. Document both the density basis and the risk assessment in your Data Protection Impact Assessment. See compliance mapping for GDPR and CCPA location data for a full regulatory clause breakdown.

How does the density-adjusted formula behave at the urban–rural boundary?

At the boundary where local_density drops below target_density, the sqrt ratio exceeds 1.0, expanding effective_radius automatically. The square-root (rather than linear) scaling prevents over-expansion in extremely sparse areas: a 10× density drop yields only a 3.16× radius increase, keeping the displaced point within a geographically plausible region rather than ejecting it across administrative boundaries.

Can the same radius configuration satisfy both k-anonymity and differential privacy simultaneously?

Yes, with careful parameter alignment. Set $r_{\text{base}} = \Delta / \varepsilon$ where $\Delta$ is the L1 sensitivity of the location query and $\varepsilon$ is the privacy budget allocated to this release. Then verify that the resulting circular displacement zone contains at least $k$ distinct records. If the k-check fails in a sparse zone, increase the radius or aggregate to the nearest administrative boundary. The two models complement each other: differential privacy governs the displacement distribution shape; k-anonymity governs the minimum population in the landing zone.

Why use the square-root trick for sampling a uniform point inside a circle?

Naively sampling $r = R \cdot U$ (linear in $U$ ) concentrates points near the centre because the annular area at radius $r$ is proportional to $r$ , not $U$ . The transform $r = R \cdot \sqrt{U}$ maps $U \in [0,1]$ uniformly over the disc area, ensuring equal probability of landing anywhere inside the fuzzing boundary — a requirement for Laplace-mechanism equivalence in differential privacy.

← Back to Spatial Fuzzing & Buffer Zone Implementation

Configuring Spatial Fuzzing Radius for Sensitive POIs

Core Calculation and Parameter Table # permalink

Sensitivity Tier Baseline Radii # permalink

Worked Numeric Example # permalink

Python Implementation # permalink

Verification Snippet # permalink

Edge Cases and Adjustments # permalink

Frequently Asked Questions # permalink

Related # permalink