Constrained minimum passage time in random geometric graphs (Q2659771): Difference between revisions

The paper under review considers a random geometric graph where \(n\) points are independently placed in the unit square \([-1/2,1/2]^{n}\) from some density satisfying mild conditions (for example, uniform distribution is covered) and we say two such are adjacent if and only if their distance is at most \(r_{n}\). We assign to each edge a \lq passage time\rq , modelled as independent identically distributed random variables with a given cumulative distribution function \(F\). A source is then inserted at \(s_{A}=(0,0)\) and a sink at some point \(s_{B}=(d_{n},0)\) and each of these is joined to all vertices within distance \(r_{n}\) of it. The main topic of interest is the minimum passage time of paths from the source to the sink. Attention focuses on paths which do not wind too much: formally, given \(K\geq 1\), a path from \(s_{A}\) to \(s_{B}\) is said to have stretch at most \(K\) if the number of edges in it (which must trivially be at least \(d_{n}/r_{n}\)) is at most \(Kd_{n}/r_{n}\). The main result gives both upper and lower bounds on the passage time from \(s_{A}\) to \(s_{B}\) of paths of stretch at most \(K\) under various technical assumptions.