Separating Two Points with Obstacles in the Plane

Weighted point separation on real regional terrain, with hypothetical straight candidate fences. The source s represents the advertised venue, Area 51 Alien Center in Amargosa Valley: TIME's contemporaneous reporting names the venue; Travel Nevada confirms its US-95 address; the point coordinate is OpenStreetMap node 4609365823 (36.6437669 N, 116.3959837 W). This is a representative mapped venue location, not a verified exact gathering position. The site t uses its approximate public location (37.235 N, 115.8111 W). The scene spans about 116.5 by 54.6 km, rotated so s-to-t runs left to right. The map has no compass or scale annotation. Elevation uses 255 zoom-12 Mapzen Terrain Tiles, about 30.5 m per source sample. All 255 source headers identify USGS one-third-arc-second National Elevation Dataset rasters: imgn37w116_13, imgn37w117_13, imgn38w116_13 and imgn38w117_13. USGS is the dataset producer; Mapzen resampled/packaged the tiles, served from AWS. OpenStreetMap did not supply the elevations. The original input is a USGS compilation: we do not assert that every underlying survey was performed by USGS. Our renderer rotates/resamples the heights and adds elevation tint and upper-left hillshade without vertical exaggeration. Source metadata and transformations are documented in graphics/area51-terrain/SOURCES.md. The first view shows only the terrain and the two points. No land boundaries, boundary legend or candidate fences are drawn in that view. The published NTTR/NNSS polygons are retained only for geographic validation. The Groom Lake outline is retained only for checking that every complete candidate fence avoids it; no lake overlay is drawn. Fourteen crossing candidates form alternative circuits. The illustrative cost is round(length/5 km + total sampled absolute elevation change/300 m), minimum 1; these are abstract units, not dollar estimates. The terrain changes the prices, not passability. The compact, minimum-total-length separator costs 85 and uses five fences. It includes the long diagonal across the ridge system. The unique weighted optimum costs 75 and uses six fences, taking the western valley detour; its enclosed area is substantially larger, and its total fence length is slightly greater. Both costs use exactly the same terrain model. A comparison reveal precedes the optimal solution. Wires connect to circular cost eyelets, and all unchosen candidates remain faded in the solution. We validate intersections, separation, optimality, uniqueness, map coverage, lake avoidance and label clearance. Sources: https://time.com/5628391/area-51-meme-explained/ ; https://travelnevada.com/extraterrestrial/area-51-alien-center/ ; https://www.openstreetmap.org/node/4609365823 ; https://github.com/tilezen/joerd/blob/master/docs/data-sources.md ; https://github.com/tilezen/joerd/blob/master/docs/attribution.md ; https://www.dreamlandresort.com/maps/NTTR_Boundaries.kmz .

Introduce points, segments, rays and polygons incrementally. First show intersecting and disjoint ray pairs, then the explicit scalar test. One inequality uses the minimum of the two fully expanded scalar products. It is positive exactly when both rays reach their supporting-line intersection in the forward direction. No determinant symbol is introduced. No vector-valued operation or cross-product notation appears. Ignore parallel/collinear and endpoint degeneracies. Then reduce segment–ray to two ray–ray tests by extending the segment in opposite directions, and segment–segment to two segment–ray tests by extending the second segment in opposite directions. Extensions are faded; the original bounded segment stays saturated. The bottom example has exactly one passing test, demonstrating why both are necessary. No written reduction formula or pseudocode.

The exact stacked plane outlines from homology-cover-objects.svg contain the same four-segment example used in the introduction and intersection-graph slide. Canonical points are top endpoints (left endpoint for horizontal segments); a has a square marker. Only ac changes sheets. Entering v costs w(v), so the initial a copy is not charged and the terminal a copy is charged once. The highlighted path costs w(a)+w(b)+w(c). Every selected segment piece, canonical marker, graph vertex, and label is highlighted; other objects fade. The final build explicitly states the main characterization, in both directions: a chosen set separates s and t exactly when the graph of its lifts connects the two copies of some segment in that set. In the weighted corollary, dist means shortest-path cost in the lifted graph of the full input, and the minimum ranges over all input segments. An arbitrary path may repeat original segments, but minimizing over both the path and the starting segment gives exact equality with the optimum separator cost. Pause on the theorem before moving to the algorithmic reminders.

Baseline algorithm for n weighted line segments. Test every pair for intersection in constant time, using the primitives already introduced. For an intersecting pair, the canonical-point paths to the intersection determine whether the two lifted edges stay within a sheet or switch sheets; this also takes constant time for line segments. Thus the lifted intersection graph is built in O(n²) time, with 2n vertices and O(n²) edges. Entering a lifted vertex v costs w(v). Run Dijkstra from c0 for each original segment c, read the distance to c1, and take the minimum, by the characterization theorem. The preceding binary-heap bound gives O(n³ log n), displayed as O-tilde(n³). The edge bound is worst-case; the reused four-segment example illustrates the construction and one search. The next slides show how biclique covers avoid listing all these edges.

The selected clique sits in a larger host graph. The intermediate selected cycle sits in a directed 5-circle-layered graph with three vertices in each part: edges go only from Vi to V(i+1 mod 5). Hence no shorter cycle exists. This is the special structural form in the sparse hardness theorem, not an arbitrary cycle graph. The drawings illustrate the respective instance types, not a literal vertex-for-vertex reduction of the small displayed host. The geometric diagram extends the original full construction to five bands. Source for circle layering and sparse hardness: Lincoln, Vassilevska Williams, Williams, Tight Hardness for Shortest Cycles and Paths in Sparse Graphs, definition in Section 2 and the sparse-cycle theorem, https://people.csail.mit.edu/virgi/6.s078/papers/sparseapsp.pdf . For fixed k, the geometric reduction has N=O(m) segments. The hypothesis is singular and quantified over all fixed odd k.

Source: current_arXiv/main.tex, Theorem k-cycle-reduction and Figure lower-bound-polylines; original lower-bounds pages 13 and 14. Replace each edge obstacle by one vertical-horizontal-vertical polyline through the midline of its row band, with the same endpoints and the same weight. The exterior vertex segments are already rectilinear and remain separate obstacles. The right figure applies this replacement to the same sparse five-band instance and selected cycle as the preceding slide: it does not insert missing graph edges, although distinct polylines can overlap. Hollow circles mark obstacle endpoints, not bends. A selected cycle plus its exterior return route still separates s from t. The proof forces one edge obstacle in each band and preserves the cycle cost plus the fixed exterior cost. For fixed k there are N=O(m) obstacles, each with at most three axis-aligned pieces. Therefore the following clique-based lower bounds also hold for weighted rectilinear polylines, yielding Omega(N^(2-o(1))) under the stated hypothesis. This does not establish that bound for axis-aligned segments or for two-piece rectilinear polylines.