📊 statistics

Shortest Path Lengths in Poisson Line Cox Processes: Approximations and Applications

This paper derives closed-form expressions and analytical bounds for the distribution of shortest path lengths in Poisson line Cox processes under one- and two-turn constraints, providing a theoretical framework to characterize the performance and dimensioning of ride-hailing services and vehicle-to-vehicle communication systems.

Original authors: Gourab Ghatak, Sanjoy Kumar Jhawar, Martin Haenggi

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gourab Ghatak, Sanjoy Kumar Jhawar, Martin Haenggi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city not as a grid of perfect squares, but as a chaotic, randomly drawn web of streets. Now, picture cars (or people) scattered along these streets like beads on a string. This is the world the paper explores: a mathematical model of a city where roads are random lines and vehicles are random points on those lines.

The researchers are trying to answer a simple but tricky question: If you are standing at a random spot on a random street, how far do you have to travel to find the nearest car?

Here is the breakdown of their findings using everyday analogies:

1. The "Manhattan" Problem (Why Straight Lines Don't Work)

In a normal city, you can't fly through buildings. You have to drive along the streets. This is called "street-constrained" travel.

The Analogy: Imagine you are at a park (Point A) and your friend is at a coffee shop (Point B). If you could fly, the distance is a straight line (like a bird). But if you must walk on sidewalks, you have to turn corners. The paper calls this the "L1 distance" (walking distance) versus the "L2 distance" (flying distance).
The Challenge: In a city with perfectly straight, grid-like streets (like Manhattan), calculating this walking distance is easy. But in this paper's model, the streets are random lines crossing at random angles. Calculating the exact walking distance to the nearest car in this messy web is incredibly hard.

2. The "One-Turn" Rule (The First Discovery)

The researchers started by simplifying the problem: What if you are only allowed to make one turn?

Scenario A: You are a random car. You are stuck on one street. You can drive forward or backward. If you don't see a car, you can turn onto a crossing street and drive there.
- The Result: They found a precise mathematical formula for the probability of finding a car within a certain walking distance. It turns out that if the streets are very crowded (high density), you find a car quickly. If the streets are empty, you have to walk much further.
Scenario B: You are at an intersection. You are standing exactly where two streets cross. You have two directions to start walking immediately (one for each street).
- The Result: Being at an intersection is a huge advantage. You are statistically closer to the nearest car than if you were just standing in the middle of a street. The paper provides a formula for this "intersection advantage."

3. The "Two-Turn" Rule (The Second Discovery)

What if you are allowed to make two turns?

The Analogy: You walk down Street A, turn onto Street B, and then, if you still haven't found a car, you turn onto Street C.
The Challenge: The math gets messy very fast because there are infinite ways to turn.
The Solution: Instead of finding the exact answer (which is too hard), the researchers created a "safety net" calculation. They imagined a slightly smaller, simpler version of the city where they only counted specific types of two-turn paths.
- The Result: This gives them an upper bound. Think of it like saying, "Even in the worst-case scenario of a two-turn search, you will definitely find a car within this distance." It's not the exact distance, but it's a guaranteed limit that is very useful for planning.

4. The "Ride-Hailing" Application (Why This Matters)

The paper uses these formulas to simulate a ride-hailing service (like Uber or Lyft).

The Insight: If a city planner assumes cars are scattered randomly in a 2D field (like birds in the sky) and calculates pickup times based on "straight-line" distance, they will be wrong.
- The Twist: For short trips, the "straight-line" guess might actually look better than reality. But for longer trips, the "straight-line" guess is dangerously optimistic because it ignores the fact that you have to drive around corners.
The Takeaway: The researchers show that allowing a driver to make just one turn cuts the average pickup distance significantly. Allowing a second turn helps a little bit more, but the biggest gain comes from that first turn. This helps city planners decide how many cars they actually need to guarantee a quick pickup.

5. The "Wireless" Application (Talking to Cars)

The paper also mentions how this applies to cars talking to each other (Vehicle-to-Vehicle communication).

The Analogy: Imagine a car at an intersection wants to send a safety message (like "I'm braking!") to the nearest car. Sometimes the signal can bounce off a smart surface (like a mirror) on a building to reach a car on a crossing street.
The Connection: The strength of that signal depends on the total distance the signal travels. By using their "one-turn" and "two-turn" formulas, engineers can predict how likely it is for a message to reach a neighbor car successfully, even if that neighbor is on a different street.

Summary

This paper is a math toolkit for understanding how far you have to walk (or drive) to find something in a random city.

Starting at an intersection is better than starting on a street.
Making one turn drastically improves your chances of finding a car quickly.
Making two turns helps a bit more, but with diminishing returns.
Ignoring the streets (assuming straight-line travel) leads to bad planning for both ride-sharing and safety communications.

The authors didn't just guess; they built precise mathematical maps (formulas) that tell us exactly how these distances behave based on how crowded the streets and cars are.

Technical Summary: Shortest Path Lengths in Poisson Line Cox Processes

1. Problem Statement

The paper addresses the characterization of street-constrained ( $\ell_1$ ) shortest path lengths within a Poisson Line Cox Process (PLCP). In this stochastic geometry model, a Poisson Line Process (PLP) with density $\lambda$ generates random lines in the Euclidean plane. On these lines, Poisson Point Processes (PPPs) with linear intensity $\mu$ are superimposed, representing entities such as vehicles or street nodes.

While the Euclidean ( $\ell_2$ ) distance to the nearest neighbor is well-understood, the $\ell_1$ distance (path length restricted to the lines) is significantly more complex due to the random orientations of the lines. The authors aim to derive exact distributions and tractable bounds for the shortest path length from a typical location to its nearest neighbor under specific routing constraints (one-turn and two-turn restrictions). This problem is critical for applications in urban transportation planning (e.g., ride-hailing) and vehicular communications, where movement is constrained to the street network.

2. Methodology

The authors employ stochastic geometry and geometric probability techniques, specifically utilizing void probabilities and Palm conditioning.

Geometric Decomposition: The core methodology involves decomposing the feasible set of path lengths. The authors explicitly evaluate the probability that no PLCP points exist within a path length $t$ (the void probability) by conditioning on the underlying PLP.
Conditional Independence: They exploit the fact that, conditioned on the PLP, the point processes on distinct lines are independent one-dimensional PPPs. This allows the factorization of void probabilities across different line segments.
Case Analysis:
- Typical Point: The analysis considers a typical point on a single line ( $L_x$ ).
- Typical Intersection: The analysis considers a typical intersection where two lines ( $L_x$ and $L_y$ ) cross. This requires a detailed geometric decomposition of the feasible path-length region along intersecting random lines, involving case-by-case evaluations of intersection angles and distances.
- Two-Turn Case: For the two-turn scenario, the authors use a feasible-set shrinking argument. Instead of characterizing all possible two-turn paths (which is analytically intractable), they restrict the analysis to a subset of admissible paths (specifically, paths where the second turn occurs after reaching a selected intermediate line). This yields a computable upper bound.
Comparison with Euclidean Models: The paper analytically compares the derived PLCP distributions against a matched-intensity planar Poisson Point Process (PPP) to quantify the "detour bias" introduced by street constraints.

3. Key Contributions and Results

A. Exact Distributions for One-Turn Routing

The paper derives closed-form expressions for the Cumulative Distribution Function (CDF) of the shortest path length under a one-turn restriction:

From the Typical PLCP Point: Theorem 1 provides an exact CDF derived by evaluating the void probability via conditioning on the PLP. The result is:
$F_D(t) = 1 - \exp\left(-2\mu t - 2\lambda t + \frac{\lambda}{\mu}(1 - e^{-2\mu t})\right)$
From the Typical PLP Intersection: Theorem 2 establishes an exact characterization for the origin being a typical intersection. This involves complex integrals ( $T_x, T_y$ ) that account for the interaction between line orientation randomness and point process density.

B. Bounds for the Intersection Case

For the intersection case, the authors provide analytically tractable bounds:

Lower Bound: Derived by considering only points on the two intersecting lines ( $L_x, L_y$ ) within distance $t$ .
Upper Bound: Derived by including intersections along these lines.
These bounds are shown to be tight in specific regimes (lower bound tight for high $\mu$ , upper bound tight for high $\lambda$ ).

C. Two-Turn Analysis

For the case allowing two turns from a typical point, the paper derives a computable upper bound on the distribution (Theorem 3). This bound is obtained by shrinking the feasible set of paths. The analysis identifies regimes where this bound is tight and compares the performance of a two-turn route from a typical point against a one-turn route from a typical intersection.

D. Transportation and Communication Applications

The paper demonstrates how these distributions translate into operational metrics:

Ride-Hailing: The results enable the calculation of expected pickup distances and service reliability (probability of pickup within a time/distance threshold). The authors show that allowing a single turn reduces expected pickup distance by approximately 31% compared to zero-turn (straight-line) constraints, while a second turn offers diminishing returns (~8% additional reduction).
Fleet Dimensioning: The derived expressions allow for the analytical determination of minimum vehicle density ( $\mu$ ) required to meet specific service guarantees, avoiding the need for Monte Carlo simulations.
Vehicular Communications (V2V): The paper qualitatively illustrates how path length distributions affect the received signal power in near-field broadcasting scenarios using Re-configurable Intelligent Surfaces (RIS) and in far-field communications. The path length determines the link budget for Basic Safety Messages (BSMs).

E. Comparison with Euclidean Planning

Theorem 4 proves that the one-turn PLCP distance distribution and a matched-intensity Euclidean PPP distribution are not comparable via first-order stochastic dominance. They cross exactly once at a critical distance $t^*$ . For short distances, the PLCP is more likely to be shorter than the Euclidean approximation; for long distances, the Euclidean approximation underestimates the path length (i.e., the PLCP path is longer). This highlights a structural bias in planning if Euclidean metrics are used for street-constrained networks.

4. Significance and Claims

The paper claims that its primary significance lies in providing the first exact closed-form characterizations of shortest path lengths in PLCPs under one-turn restrictions, a problem previously considered open due to the random orientation of lines.

Analytical Rigor: The work moves beyond simple approximations (which the authors show can lead to incorrect recursive equations) to provide exact distributions and rigorous bounds.
Practical Utility: The results serve as a "practical analytical engine" for transportation system design, allowing for direct computation of service guarantees and fleet sizing without simulation.
Insight into Routing Flexibility: The analysis quantifies the trade-offs between origin selection (point vs. intersection) and routing flexibility (one vs. two turns), revealing that a one-turn route from an intersection can outperform a two-turn route from a typical point under certain density parameters.
Limitations: The authors modestly note that the two-turn result is an upper bound derived via a shrinking argument, and an exact characterization for an unrestricted number of turns remains an open problem. The models are intended as benchmarks for short-range/last-mile accessibility rather than general navigation with unlimited turns.