CS Paper Radar

Voronoi-Markov chain and spatial entropy for point pattern analysis

James C. Mathews, Francisco Couzo, Aleksandr Petrov, Avijit Chatterjee, Saad Nadeem

cs.IT ·submitted 2026-09-28 19:28 UTC · v1
top venuecode/data

Abstract

In this paper, we revisit the concept of entropy in the spatial context with the aim of deriving computable and interpretable metrics for point pattern analysis in domains such as histopathology. We discuss stochastic point process assumptions like Poisson homogeneity and Simple Sequential Inhibition (SSI) and review established results for Voronoi and Delaunay tilings of point sets for their potential to provide null distributions for rigorous empirical hypothesis testing. We present (1) a novel "dense basin entropy" defined in terms of the Ord distribution supported on Voronoi basins, which is shown to be sensitive to clustering, and (2) a related Markov chain designed as a simplification or approximation of Brownian motion in the underlying planar domain. We investigate bounds on the dense basin entropy in the SSI regime and in empirical data, and show that the entropy rate and spectral gap of the Markov chain lead to sharp discrimination metrics. Finally, we demonstrate a generalization to multiple-set analysis via aggregation of one set over the Markov invariant measure for another. Simulations and experiments in histopathology show that our proposed metrics offer insights complementary to other instantiations of entropy in spatial analysis. The code can be found on our SMProfiler GitHub: https://github.com/nadeemlab/SMProfiler.

Comment
NeurIPS'26 Main Conference (Accepted)

Closest papers

Nearest neighbours by meaning across the whole index.

A Survey of Typical-Cell Volume Distributions in Poisson--Voronoi and Poisson--Delaunay Tessellations: Analytical Theory, High-Dimensional Limits, and Wireless Applications

cs.IT ·2026-08-12 ·Minghua Xia, Tian Shi, Wenkunn Wen
publishedsurvey similarity 0.57
Abstract · 23 pages, 3 figures, 3 tables, Accepted for publication in IEEE Access

Random spatial tessellations generated by point processes provide fundamental models for proximity, space partitioning, and local geometry in stochastic systems. Poisson--Voronoi and Poisson--Delaunay tessellations induced by homogeneous Poisson point processes form a canonical dual pair used in stochastic geometry, computational geometry, spatial statistics, and wireless-network analysis. Their typical-cell volume distributions provide important geometric inputs for modeling coverage, traffic load, clustering, connectivity, and other system characteristics. Despite extensive study, the literature remains analytically asymmetric. For Poisson--Voronoi cell volumes, exact integral representations exist in certain planar settings, while a recent scale--shape factorization provides an exact general-dimensional representation with conditional Gamma structure. However, the normalized shape laws and unbounded facet-count mixture remain implicit, and tractable unconditional closed-form distributions are unavailable. Practical modeling therefore relies largely on simulation, moment characterizations, and empirical approximations. By contrast, Poisson--Delaunay simplex volumes admit dimension-explicit PDFs, CDFs, and moment formulas derived through Mellin-transform analysis and Meijer's \(G\)-function representations. Motivated by this contrast, this paper surveys typical-cell volume distributions in Poisson--Voronoi and Poisson--Delaunay tessellations. We review the main analytical methods, synthesize exact and approximate results, summarize emerging high-dimensional limits, and discuss wireless-network applications, including load modeling, cooperative transmission, and three-dimensional architectures. We also identify open problems concerning unconditional Poisson--Voronoi distributions, non-Poisson spatial models, data-driven geometric inference, and dimension-aware network modeling.

0.62

Visibility graphs of irregularly sampled two-dimensional fields via Voronoi tessellations

cs.CG math.DScond-mat.stat-mechphysics.data-an ·2026-11-12 ·Francisco J. Muñoz, Juan Carlos Nuño
similarity 0.52
Abstract · 10 pages, 5 figures

Visibility graphs map a time series into a network by linking two data whenever the straight line between them is not obstructed by intermediate data. Their extension to two-dimensional fields has so far been restricted to regular lattices, where visibility is checked along a finite number of lattice directions. We propose a definition for scalar data sampled at arbitrary, irregularly scattered points of the plane. Each point is assigned its Voronoi cell, so that the data become a landscape of prisms, and two points are linked when the line of sight between them clears the cells crossed by the connecting segment. This yields horizontal ($\HVGV$) and natural ($\NVGV$) Voronoi visibility graphs that reduce exactly to the classical horizontal and natural visibility graphs when the points are collinear, contain the Gabriel graph of the point set, and can be built by an exact walk through the Delaunay triangulation. For uncorrelated heights, the horizontal graph depends only on the ranks of the data, so its statistics are independent of the marginal distribution. The probability that two points see each other is $2/[(M+1)(M+2)]$, where $M$ is the number of Voronoi cells crossed, which reduces the problem to the geometry of the tessellation. For Poisson points this gives a degree distribution with a scale-free tail $P(k)\simeq(π^3/4)\,k^{-2}$ and a mean degree that grows as $(π^3/8)\ln N$, in contrast with the finite value $\langle k\rangle=4$ of one-dimensional series. Two dimensions are therefore the marginal case in which isotropic horizontal visibility ceases to be local. Numerical simulations with up to $N=1.28\times10^5$ points support these predictions.

0.28

ToPos: Automated Optimal Positioning on Topographic Manifolds using Constrained Geodesic Voronoi Decomposition

cs.RO ·2026-09-04 ·Rajesh Raveendran, Akseli Vanhamaa, Jaakko Suutala, Antti Tikanmäki, Juha Röning
published similarity 0.51
Abstract · ©2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future m…

Reliable autonomous mapping, environmental sampling, last-mile logistics, and infrastructure deployment depend on the optimal surface area-balanced distribution of Spatial Reference Sites (SRS). Conventional 2D Euclidean methods often fail in high-relief environments by neglecting topographic variations and physical obstructions. This leads to significant planimetric distortion, spatial clustering, and the placement of targets in inaccessible or shadowed regions, compromising both data integrity and operational safety. This paper introduces ToPos, an automated framework for TOPography-aware Optimal Sampling on topographic manifolds. We treat the terrain as a discrete 2-dimensional manifold embedded in 3D Euclidean space and replace standard flat-map distances with non-Euclidean geodesic distances that follow the actual surface geometry. The point distribution is formulated as an optimization problem using a Constrained Geodesic Voronoi Decomposition, solved via a Riemannian Nesterov Accelerated Gradient (NAG) engine. Our approach restricts target locations to a feasible "safe zone," accounting for non-traversable slopes, vegetation, environmental occlusions, etc. Through evaluations on non-convex sinusoidal manifolds, we show that ToPos mitigates planimetric distortion by utilizing geodesic metrics. This approach results in a $\sim$74% improvement in optimal surface area-balanced distribution, as measured by the coefficient of variation (CV) of the Voronoi cell areas. The framework is architected as a Geographic Information System (GIS)-ready micro-service to bolster the mentioned applications. Index Terms: Topographic Manifolds, Geodesic Voronoi Decomposition, Infrastructure Deployment, 3D Mapping, Spatial Sampling, and Non-Euclidean Optimization.

0.35

Generative diffusion in long-range correlated landscapes: Speciation cascade and the foam structure of the score

cs.LG cond-mat.dis-nncond-mat.stat-mech ·2026-11-02 ·Jerome Garnier-Brun, Giulio Biroli, Marc Mézard, Jean-Philippe Bouchaud
similarity 0.50
Abstract · 25 pages, 7 figures

While state of the art for image and video generation, the fundamental reasons for the effectiveness of generative diffusion remain unclear. In particular, the observed advantage of following an entire reverse process with respect to single-shot or autoregressive methods, and for what type of data it may hold, is not well understood. In this work, we aim to better understand the role of the reverse process by considering a complex yet analytically tractable data model, the Gibbs measure of a high-dimensional Gaussian random potential with long-range correlations. Focusing on the exact score, we show that the speciation threshold, in which a trajectory commits to one class of the data, becomes a speciation window, in which the reverse process progressively resolves the Parisi tree of pure states of the full replica-symmetry breaking measure, committing to ever finer branches down to a single pure state. Importantly, these commitments take place at noise levels where the noisy sample distinguishes the pure states only through an energy of order one, beyond the reach of standard replica saddle points. Constructing a Larkin argument suited to such $O(1)$ energy gaps, we describe the score as a foam, with slab-like cells separated by shock-like boundaries. In the variance-exploding process we consider, this window is followed by a shrinkage of the samples towards the data support, and finally by reconstruction within the selected pure state. The denoising error of the exact score follows these stages, dropping during the speciation window with a profile set by the Parisi function alone, and then within the selected state. We believe that the generative foam we describe, and in particular the boundaries between cells, could play an important role in determining where the errors of trained diffusion models redistribute the mass of the generated samples when the data are long-range correlated.

0.29

Multiscale Closing Index (MCI) for measuring structural similarity between 2D point sets

cs.CG math.MGcs.CV ·2026-11-06 ·Nicolò Zava, Angel Franco-Alvarez, Samy Blusseau, Santiago Velasco-Forero, Maria-Jose Jimenez
similarity 0.49
Abstract

We introduce Multi-scale Closing Index (MCI), a new dissimilarity measure for evaluating the alignment of two 2D point sets. MCI is bounded between 0 and 1 and is based on multiscale mathematical morphology operations, with smaller values indicating greater structural agreement. The measure was motivated by the need to assess the quality of registration between point sets representing cell populations in biological images. To evaluate its behaviour under controlled conditions, we generated synthetic point clouds from Perlin-noise-based spatial structures, following established approaches for simulating biologically plausible spatial organization. We assessed MCI between those point clouds and different transformed versions, obtained by local perturbation, point removal, translation, rotation and addition of impulsive noise. Across these experiments, the dissimilarity MCI increased gradually and consistently with perturbation severity, while showing a clear discontinuity between clouds originating from the same underlying spatial structure and point clouds generated from different structures. We further compared MCI with commonly used point-set distances, including Hausdorff-based measures and Sliced Wasserstein distance. These experiments show the ability of MCI to capture structural agreement and quantify deviations between point sets, highlighting its potential as a complementary metric for evaluating two-dimensional point-set registration.

0.22

A Unified Framework for Training-Dataset Aggregation and Exact Machine Unlearning via Gibbs Probability Measures

cs.IT stat.MLcs.LG ·2026-11-03 ·Yaiza Bermudez, Samir M. Perlaza, Iñaki Esnaola
similarity 0.49
Abstract · Submitted to the IEEE Transaction on Information Theory

In this paper, three operations on Gibbs probability measures are studied: renormalization, normalized log-linear combination, and nesting. The resulting measures are shown to be Gibbs probability measures with explicit expressions for their objective functions, reference measures, and regularization factors. These measures are further characterized as unique solutions to optimization problems involving linear combinations of the original objective functions, subject to either relative entropy regularization or relative entropy constraints. When the reference measures are probability measures, geometric interpretations of these three operations are established involving Pythagorean identities and exponential geodesics.A central result is the equivalence between nesting and normalized log-linear combinations of Gibbs probability measures. These results are then applied to supervised machine learning with Gibbs algorithms, which are represented by Gibbs probability measures. In this context, either through nesting or log-linear combinations, Gibbs algorithms trained on local datasets are used to form new Gibbs algorithms trained upon the aggregation of all local training datasets. Interestingly, the parameters of such operations, determine the weights of each training data point on the aggregated dataset. %Operations on local Gibbs probability measures are shown to control the contributions of training data. This observation is leveraged for achieving: (a) exact machine unlearning in centralized, decentralized, and federated learning systems; and (b) centralized-equivalent performance, in the sense of producing algorithms trained on the aggregation of all local datasets in decentralized and federated learning .

0.09

TraHist: Fast and Accurate Cardinality Estimation for Trajectory Data (Extended Version)

cs.DB ·2026-10-15 ·Yujeong Jo, Incheol Baek, Changbeom Shim, Yon Dohn Chung
top venue similarity 0.49
Abstract · Extended version of the paper to appear in PACMMOD Vol. 4, No. 6 (SIGMOD 2027)

Cardinality estimation is fundamental for query optimization in database systems. Histogram-based estimators are widely used for their simplicity and efficiency but rely on point-centric partitioning that assumes record independence. This assumption breaks in trajectory data, where records from the same moving object show strong spatiotemporal dependencies. Conventional axis-aligned histograms therefore fragment trajectories across partition boundaries, leading to overestimation through duplicate counting. This error reflects a structural limitation of partition boundaries that are misaligned with trajectory-induced density patterns. To this end, we propose TraHist, a histogram-based estimator approximating density-aligned partitioning via efficient grid-based propagation. TraHist builds density-adaptive rectilinear buckets to preserve trajectory continuity and local density coherence while keeping histogram efficiency. Experiments on large-scale real-world datasets show that TraHist reduces estimation error by over 20x relative to the strongest competing estimator in query regimes where trajectory fragmentation is a dominant source of estimation error, while maintaining sub-millisecond query latency and competitive construction cost.

0.43

An information identity reveals the geometry of deviation events

cs.IT ·2026-09-29 ·Akshay Balsubramani
similarity 0.49
Abstract

In a deviation event, the empirical measure of $n$ independent draws lands in a set of distributions. The exponent of its probability splits, at every $n$, into two nonnegative terms. The first is the rate: $n$ times the relative entropy, from the population, of the distribution of a typical draw under the event. The second is the dependence that conditioning induces among the draws, measured by their total correlation. Their relative sizes depend on the geometry of the set. This paper focuses on this exact split and on the geometry that the interplay of its two terms reveals. The dependence vanishes exactly when the event confines every draw to a single set, and the classical rate of that constraint is exact. On a set invariant under a compact group that fixes the population and leaves no invariant set of intermediate probability, the rate vanishes; uniform convergence over a hypothesis class that such a group permutes is one. On a half-space whose threshold sits a fixed number of standard errors above the mean, the fraction of the exponent that is dependence tends to a function of the event's probability alone. On a set split into pieces, the dependence is the pieces' average plus $n$ times the Jensen-Shannon divergence of their marginals, minus the entropy of their weights. The split extends to a general reference law. When the information projection is such a law, the split gives the exact value of the expectation in the exponential change of measure to the projection.

0.22