A fast method to estimate an earthquake epicentral region from the very first P-wave arrivals is relevant in the context of early warning and rapid response systems. Arrival-time order location (AOL) uses the sequence in which an array of sensors detects an event to constrain the epicentral region based on simple geometrical relations. No velocity model is needed. This article recasts AOL using the theory of spatial tessellations and describes a solution based on higher order Voronoi diagrams. The implementation can take advantage of modern computational geometry algorithms. The required calculations are fast and are suitable for a real-time system.