# Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.

An agent can move in the area at constant unit speed. When moving, it marks all nodes within distance $d$ from it ($d$ is Eucliean distance rather than number of hops). It aims at finding an itinerary such that given the time duration $T$, it can mark as many nodes as possible. In other words, the agent wants to find a path of length $l=T$ along which it can mark as many nodes as possile.

Under such setting, if the path is chosen randomly (e.g., the agent goes straightly towards a random direction for the entire time duration $T$), which is a natural strategy, then the number of nodes covered is $\frac{NT}{D^2}$. This gives a reference for comparison. Now I want to derive the expected number of covered nodes (or an upper-bound) for an optimal path, i.e., if the agent strategically chooses an optimal path, what is the number of nodes covered in average?

• Can you please edit to make this more precise. You are talking about random geometric graphs, right? If nodes are distributed with Poisson density $\lambda$ on $\mathbb{R}^d$ there is no optimal path: There is a sequence of paths where the number of nodes covered is unbounded. So you need to specify the domain. Also, it is not clear whether the agent is restricted to the graph (in which case, how to move in a straight line), or not (in which case, $d$ is Eucliean distances rather than number of hops, and we might as well just talk about node locations and ignore the graph). – user25199 Jun 30 '14 at 9:26
• @Carl. Thanks Carl for your comment. I have reformulated the problem. – lchen Jun 30 '14 at 9:41
• Thanks - clearer now. A couple of further remarks: 1. Fixed $N$ normally behaves similarly to fixed density $\lambda=N/D^2$ but the latter is easier to work with since the nodes in disjoint subsets are independent. 2. The area covered in duration $T$ (assuming far from the boundaries) is $2dT+\pi d^2$ if I understand correctly, so I would expect the average number of nodes covered (without optimising) to be about $(2dT+\pi d^2)N/D^2$. – user25199 Jun 30 '14 at 9:51
• The expected number of points covered is directly proportional to the area passed over by the disc of radius $d$ as it is dragged along the path followed by the agent, so this isn't really anything to do with random graphs. This area doesn't seem to depend very much on the actual path followed, unless you do something obviously silly: for example, tracing an arc of length $l$ of a circle gives the same result whatever the radius $l$ of the circle is, provided $l \leq r$ (to prevent wrap-around). – Ben Barber Jun 30 '14 at 10:32
• @Ben I agree it is not a random graph question. Choosing a region with a higher than average density of nodes, it is presumably possible to gain a further logarithmic factor. – user25199 Jun 30 '14 at 10:42