Geometric properties of Poisson matchings

DOI10.1007/S00440-010-0282-YzbMATH Open1225.60082arXiv0909.0575OpenAlexW2071274211MaRDI QIDQ718894FDOQ718894

A. E. Holroyd

Publication date: 27 September 2011

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Suppose that red and blue points occur as independent Poisson processes of equal intensity in R^d, and that the red points are matched to the blue points via straight edges in a translation-invariant way. We address several closely related properties of such matchings. We prove that there exist matchings that locally minimize total edge length in d=1 and d>=3, but not in the strip R x [0,1]. We prove that there exist matchings in which every bounded set intersects only finitely many edges in d>=2, but not in d=1 or in the strip. It is unknown whether there exists a matching with no crossings in d=2, but we prove positive answers to various relaxations of this question. Several open problems are presented.

Full work available at URL: https://arxiv.org/abs/0909.0575

Recommendations

• Poisson matching
• Minimal matchings of point processes
• Multicolour Poisson matching
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Euclidean semi-matchings of random samples

zbMATH Keywords

point processmatchingPoisson process

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Geometric probability and stochastic geometry (60D05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• Stationary random graphs with prescribed iid degrees on a spatial Poisson process
• Connected allocation to Poisson points in \(\mathbb R^{2}\)
• Poisson matching
• Trees and matchings from point processes
• Translation-Equivariant Matchings of Coin Flips on ℤ^d

Cited In (14)

• Ergodicity of Poisson products and applications
• Poisson matching
• Optimal stationary markings
• Multicolour Poisson matching
• Combinatorial Optimization Over Two Random Point Sets
• There is no stationary \(p\)-cyclically monotone Poisson matching in 2d
• There is no stationary cyclically monotone Poisson matching in 2d
• Trees and matchings from point processes
• Matching random colored points with rectangles
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Invariant embeddings of unimodular random planar graphs
• Minimal matchings of point processes
• Coalescence on the real line
• Factors of IID on Trees

This page was built for publication: Geometric properties of Poisson matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q718894)