Six ways to start a search

Authorship and source

Pedro M. M. de Castro
derived from Olivier Devillers and Pedro Machado Manhães de Castro. A Pedagogic JavaScript Program for Point Location Strategies. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SoCG ’11). ACM, 2011, pp. 295–296. doi:10.1145/1998196.1998244.

We would like to thank Olivier Devillers, coauthor of the source paper. Tools for computational exploration and implementation: OpenAI Codex and Anthropic Claude.

This interactive visualization presents the six strategies compared in that paper. The original demonstration was developed by Pedro Machado Manhães de Castro and Olivier Devillers and hosted at INRIA. Authorship of the underlying algorithms is discussed through the paper’s references; presenting the comparison does not imply inventing all six strategies.

Original demonstration and supporting material · Point-location research

The six strategies

All strategies use visibility walks in counterclockwise Delaunay triangles. An edge qualifies when its line separates the query from the triangle. At each step, one qualifying edge is selected uniformly using a seeded pseudorandom generator. A query on an edge may belong to either incident face.

The fixed sample and query memory have size k = max(1, floor(cube root of n)), where n includes the square corners. Each keep strategy stores the coordinates and located face of its last k interior queries. Queries outside the frame do not enter memory or replace the last interior face.

Initially, a strategy with no previous query starts in face 0. Hierarchy search starts in face 0 of the highest level. Climbing chooses the first promoted real vertex in the current face’s local order. Descent chooses the closest vertex of the located upper face and an incident face in the level below. These operational choices make details left open by the short paper explicit.

Hierarchy and frame

The four corners of [0, 1]² appear at every level and are excluded from climbing promotions. Each surviving real vertex is independently promoted with probability α at the next level. Sampling stops when no real vertices survive, no points are removed, or seven levels have been built. Thus the constant promotion rule is subject to the finite display limit and the retained frame.

The available probabilities, 0.25, 0.45 and 0.65, make the hierarchy visible with small point sets. They are visualization settings, not performance recommendations. Local queries take bounded small steps from the preceding query. Moderate steps use a wider window; Uniform queries sample the square independently. Local with jumps adds an independent query every eighth step; Alternating poles moves between two neighbourhoods; Raster and Transect follow fixed, repeating paths. The seed controls pseudorandom choices; rebuilding resets each path.

Relation to the historical program

The current visualization implements the descriptions in the paper with three explicit differences from the preserved 2011 JavaScript:

• The walk randomly chooses among all admissible successor edges. The historical program scans edges in a fixed order and avoids an immediate return to the preceding face.
• Promotion uses a constant conditional probability α per level. The historical loop compounds the conditional probability at successive levels.
• The keep strategies remember actual query coordinates and their located faces. The historical program stores a representative vertex of the located face.

These choices change trajectories and operation counts. The experiment does not reproduce historical traces and does not claim experimental equivalence to the C++/CGAL implementation discussed in the paper.

Geometry and counters

Triangulation begins with the convex hull of the actual points, uses edge flips to make its initial fan Delaunay, and inserts the remaining points through empty-circle cavities. Identical binary-coordinate duplicates are removed. Collinear boundary points and cocircular configurations are allowed.

Orientation uses a conservative floating-point filter with an exact integer fallback. Circle tests use exact integer arithmetic on the binary floating-point coordinates received. Decimal input is still rounded when converted to a JavaScript number. No tolerance defines collinearity or cocircularity.

A visit is an entry into a triangle at any level, including revisits. Crossings and level changes are separate trace events. Distance tests count the candidate points scanned for landmark selection and vertex choices during descent. Squared distances are compared exactly for the received binary coordinates, including very small separations. The displayed totals cover the already completed query while playback reveals its events. These are illustrative operation counts, not running-time benchmarks.

The limits are 180 input points, four frame corners, seven levels, 2,000,000 construction operations and 20,000 operations per strategy per query. The computation is synchronous; Pause and Cancel affect playback and subsequent sequence queries. The implementation is intended for teaching and exploration, without a formal correctness proof or a claim of production-library equivalence.

Reading the visualization

Each panel chooses its representation automatically. The first three strategies use the base plane; hierarchy and climbing strategies show connected axonometric levels together with a larger, top-down view of the active level. The column through q and vertex connectors preserve the same coordinates across levels. The projection is fixed; it does not change the search.

Blue arrows show visit order between triangle centres, not a geometric straight-line trajectory. The initial face has a dashed outline. Crossing edges, upward transfers and downward transfers have different colours and labels. An outlined, hatched triangle marks the answer. The Detail button opens thin triangles in a separate enlarged view, with its scale and cropped distant corners stated. It never covers the main map.

Sampled vertices are square markers labelled with vertex IDs. Remembered queries are circles labelled by age: 1 is the most recent. All candidates used to choose the start remain visible during playback. After the last event, keep panels show the updated memory and say which query entered or left. Memory starts empty; the first search uses face 0. Label offsets and leader lines separate close markers without moving their actual coordinates. The separate Detail view shows subpixel separations; coincident coordinates are stated explicitly. On narrow screens, a labelled level strip replaces the side stack; its arrows indicate transitions between levels, not a spatial projection. Each level label includes its vertex count.

All six searches are computed for every query. Playback follows only the visible panels and ends when they finish. The current event never announces a final face early. The scoreboard identifies calculated totals and accumulates counts since the last reset or point-set rebuild; changing coherence does not silently reset it. These counts are not timings. Motion-reduction preferences start each query paused. Space toggles playback, Left/Right step through events, and Home/End jump to the first/last event. Within the map, arrows move a target and Enter queries it.

Point sets and provenance

The gallery contains 20 deliberately different examples. Real data are measured or recorded locations, selected and transformed into planar coordinates. Derived data are new samples constructed from a real source geometry. Synthetic sets are mathematical or procedural constructions; their application names describe a scenario, not field observations.

Every geographic set is projected to a documented plane before a uniform translation and scaling into the square. Latitude and longitude are not treated as Cartesian distances. The four square corners are artificial, and the triangulation can cross water, coastlines, gaps and aisles: no barriers, routes or geographic constraints are represented.

Fixed entries preserve order and their received binary64 coordinates. No universal grid rounding, hidden jitter or epsilon deduplication is applied. Exact repeats remain in the input and are merged by the core, retaining the first occurrence. The Iris example has 150 observations and 102 distinct petal-dimension pairs. Source IDs and multiplicities are retained in its downloadable manifest.

The three original presets retain their original generator and seed behaviour. Their names now distinguish square clusters from Gaussian clusters, and a ring with variable radius from an exact circle. Fixed entries have frozen coordinates: changing Seed changes the hierarchy, fixed sample, walks and random query paths, but not their point positions. Rebuilding clears all query memory, accumulated counts and playback.

Each fixed entry offers a JSON manifest with original coordinates or construction parameters, selection order, transformations, attribution, limitations and a checksum of the ordered planar coordinates. “Download current points” exports full round-trip decimal coordinates in the importable x y format. All examples contain at most 180 input points, before the core removes exact duplicates; no silent truncation is performed.

Synthetic entries include an exact grid and a separately labelled jittered grid; an adaptive band; warehouse aisles; orchard rows with deliberate gaps; three sensor clusters with an exclusion zone; a completed Bridson Poisson-disk sample; exact collinear and cocircular constructions; a thin strip; and a parabola. Their manifests specify spacing, order and generator parameters. They are illustrations, not meshes validated for the suggested applications.

Typography and local assets

Latin Modern, a family associated with TeX typesetting, is used for headings, explanatory prose and the italic query symbol. Inter is used for controls, counts and canvas labels. Latin Modern Mono is reserved for exact coordinates in the inspector. Drawing waits for the canvas font and repaints after subsequent font loads.

The fonts are served locally. Original, unmodified Latin Modern OpenType files are distributed under the GUST Font License; the font package notice and file manifest record their origin. Interface pictograms are local SVG shapes, not font glyphs or remote resources.