Optimal exponential memory for sequential Euclidean connections: edge-power costs and phase transitions
Pedro M. M. de Castro
arXiv, preprint, v2
Research account
Sequential Euclidean connections with exponential memory
Related publications are listed separately below. The illustrated account describes their shared research context.
Sequential Euclidean connections with exponential memory: distributional performance and adversarial robustness
Pedro M. M. de Castro
arXiv, preprint, v2
Choosing where to move or connect next is a recurring problem when data or requests arrive sequentially. In computational geometry, the starting point of a walk affects the distance travelled to locate the next query in a triangulation. In operations research, a mobile facility must balance movement with the remaining distance to serve each request. In communication networks, adding nodes through relays or aggregation points creates a related tradeoff between updating the network and paying for long connections. We study a simple geometric model shared by these motivations. A single moving point retains the past through exponential memory: after each arrival, it moves a fixed fraction of the way toward the new point. This lets the state respond to persistent changes while smoothing isolated jumps.
We analyze how this memory controls connection lengths, both for uniformly distributed points in a ball and for arbitrary input sequences. Choosing the memory according to the number of points achieves the same leading expected total length as connecting every point to the center of the ball. We also obtain sharp worst-case bounds, allowing the benefit under random input to be weighed against sensitivity to unfavorable sequences.
The same construction produces a tree whose spine joins successive memory positions, with branches leading to the input points. This raises a related optimization problem when the cost of an edge is a power of its length. Splitting a connection into a spine edge and a branch preserves total length, but changes this cost. We show how this change alters the optimal memory, with a transition at power one and distinct scaling regimes near it. Together, the two studies explain how remembering the past and dividing connections shape the cost of a sequential geometric construction.
The work is developed in two arXiv preprints. The analysis of connection lengths and robustness can be found here, and the study of edge-power costs and optimal memory here.