Theta Graph¶

A finite point set is joined sparsely by selecting, in each angular cone at each point, the neighbor with the nearest projection onto the cone's axis.

Version: v1 · 2026-10-31 · History
Domain-specific #: 14589
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Geometric Spanners, Proximity Graphs → Computer Science & Software Engineering
Aliases: Θ-graph, Geometric theta graph

Core Idea¶

A geometric Θ-graph is built from a finite set of planar points by placing k ≥ 3 equal angular cones with a shared orientation around each point and, in every nonempty cone, choosing the point with the smallest projection distance onto that cone's bisector. The resulting selected segments form a sparse geometric graph. With k fixed, each vertex chooses at most k outgoing edges, so the undirected union has at most kn selected edges before duplicates. The distinction from a Yao graph is exactly the ranking rule: Yao uses Euclidean distance to the candidate, not its projection onto the cone axis.^[1]^[2]

For appropriate k, Θ-graphs are geometric spanners: every point pair has some graph path whose total Euclidean edge length is bounded by a constant multiple of their straight-line distance. That existence statement must not be conflated with a claim that a simple local router always finds such a path. Bonichon and colleagues proved Θ₆ has spanning ratio 2 via its half-Θ₆ subgraph; a separate Θ₅ theorem proves a weaker finite bound and explicitly shows that traditional closest-in-destination-cone routing can make very long paths even when a short path exists.^[1]^[3]

How would you explain it like I'm…

Pizza-Slice Dot Connector

Imagine a bunch of dots on paper. Each dot cuts the space around it into the same few pizza slices, all turned the same way. In each slice, it draws a line to the dot that is closest along the middle of that slice. All those lines together make a Theta Graph.

Cone-Picking Point Network

A Theta Graph is a way to connect a bunch of points on a flat surface using only a few lines. Around each point, you draw the same number of equal pie-slice 'cones,' all pointing the same way. In each cone that has other points in it, you pick the point that is closest when you measure along the cone's middle line, not just straight-line closest, and connect to it. A similar graph called a Yao graph picks the straight-line closest point instead. With the right number of cones, you can always travel between any two points along the lines without the trip being more than a fixed number of times longer than going straight, though a simple step-by-step rule might not find that short route.

Bisector-Projection Spanner Graph

A Theta Graph connects a finite set of points in the plane. Around each point, place k (at least 3) equal-angle cones with the same orientation. In each nonempty cone, choose the point whose projection onto the cone's bisector (its center line) is closest, and add an edge to it. Each point adds at most k edges, so the graph is sparse. A Yao graph differs only in ranking candidates by straight-line distance instead of projection. For suitable k, Theta graphs are spanners: for every pair of points, some path in the graph has total length at most a constant times their straight-line distance. But that a short path exists doesn't mean a simple local routing rule will find it.

A geometric Θ-graph is constructed from a finite planar point set by partitioning the plane around each point into k ≥ 3 equal-angle cones with a common orientation, and in each nonempty cone connecting the point to the candidate with the smallest projection distance onto that cone's bisector. Each vertex selects at most k outgoing edges, so the undirected union has at most kn edges before removing duplicates, making it sparse for fixed k. The Yao graph uses the same cones but ranks candidates by Euclidean distance; the ranking rule is the precise difference. For appropriate k, Θ-graphs are geometric spanners: every pair of points is joined by some path whose total Euclidean length is at most a constant multiple of their straight-line distance. This is an existence statement, distinct from whether a local routing rule finds such a path. Bonichon and colleagues proved that Θ₆ has spanning ratio 2 via its half-Θ₆ subgraph, while a separate Θ₅ result proves a weaker finite bound and shows that traditional closest-in-destination-cone routing can produce very long paths even when a short one exists.

Structural Signature¶

Sig role-phrases: planar point set; equal angular cones; cone bisector; projected-nearest selection; sparse edge union; conditional path stretch.

Points: vertices are embedded in Euclidean space, so distances and directions are defined.
Cones: each vertex partitions directions into k angular sectors; boundary/tie conventions must be specified for degenerate point positions.^[1]
Reference axis: each cone has a fixed bisector on which candidate positions are orthogonally projected.
Choice: select the candidate with nearest projection along that bisector, at most one per nonempty cone at a vertex.^[1]^[2]
Edges: take selected segments as directed arcs or their undirected union; the two interpretations are not interchangeable for routing or degree statements.^[1]^[4]
Spanner claim: compare shortest graph-path length with Euclidean point distance under a proved k-specific bound; it is not the edge count or a single next-hop guarantee.^[1]^[3]

Condensed: embedded points + cones + bisector projection minimum + selected edges = Θ-graph; stretch requires a theorem for the stated variant.

What It Is Not¶

Not a Yao graph: the latter picks Euclidean-nearest candidate in each cone. The two choices can disagree.^[2]
Not necessarily a complete Euclidean graph: the Θ construction selects only certain edges, though small point sets or particular configurations can still yield a complete graph.
Not a universal 2-spanner for every k: Θ₆ has a 2 bound; Θ₅ has a larger established upper bound. Fewer cones may only yield connectivity or worse properties.^[1]^[3]^[2]
Not automatically a short greedy route: a graph's existence of short paths does not guarantee the traditional local choice finds one; Θ₅ supplies a source-attested warning.^[3]
Not automatically a wireless-network topology: real radio range/interference constraints can remove the geometric edges used in a complete Euclidean point-set theorem. A deployment needs an independently justified connection between its feasible links and the chosen geometric graph.
Not the unrelated graph-theory “theta graph” of three internally disjoint paths between two vertices: this candidate is the cone-based geometric construction.

Scope of Application¶

The direct mathematical habitat is a finite planar point set whose complete Euclidean graph is the reference. The question is whether a sparse selected-edge graph preserves pairwise distances within stretch t. Bonichon, Gavoille, Hanusse and Ilcinkas proved that for general-position planar sets, half-Θ₆ coincides with a triangular-distance Delaunay structure and that the full Θ₆ graph is a 2-spanner. The factor 2 compares best available paths in the undirected geometric graph with direct Euclidean distance; it does not promise that every routing policy obtains factor 2.^[1]

Bose and coauthors' Θ₅ study supplies a deliberately different cone count. They established a spanning-ratio upper bound √(50+22√5) ≈ 9.960 and constructed a lower bound ≈3.798. The same paper warns that the traditional destination-cone routing path can be arbitrarily long relative to the straight-line distance despite the graph's spanner property. Thus “select one edge per direction” alone is not enough to announce a particular stretch or local forwarding guarantee.^[3]

A later original routing study analyzes algorithms on Θ₆ and half-Θ₆, carefully distinguishing the routing ratio of an online procedure from the graph's shortest-path spanning ratio. Those algorithmic guarantees are additional constructions and assumptions, not defining properties of every Θ-graph.^[4]

Clarity¶

Fix the cone orientation, k, whether ties/boundary points occur, and whether an edge is treated as directed or undirected. “Nearest” without “by projection onto bisector” changes the identity to Yao. Define stretch as max over point pairs of graph shortest-path length divided by their Euclidean distance. At most kn selected arcs is a sparsity bound, not an automatic short-path bound. Conversely, the Θ₆ proof's 2-spanner result is not a statement that each selected edge is at most twice some other edge.^[1]^[2]

The assertion that naive cone-by-cone routing always follows a short path is too broad. A constructive spanner proof can establish some short path without giving the naive local forwarding rule the same bound; the Θ₅ paper explicitly separates these. The wireless setting is also deferred: a radio node may not be able to connect to the point the unconstrained Euclidean construction would select.^[3]^[4]

Manages Complexity¶

The construction reduces O(n²) potential point pairs to O(kn) selections while retaining a provable distance-approximation property for suitable variants. The sparse graph makes spatial neighborhoods tractable. The compression is not free: fewer cones or variant changes alter stretch, and online routing with local information is harder than proving that a path exists. Θ₆ and Θ₅ demonstrate this dependence concretely rather than supporting a generic “sparser is always good” statement.^[1]^[3]

Abstract Reasoning¶

To classify a candidate graph, draw cones at one vertex, project every point in a cone to the bisector, and select the least positive projected distance. Repeat at all vertices under a fixed tie convention. Then separately ask: how many edges were chosen, what is the shortest-path stretch theorem for this k, and what algorithm (if any) discovers a good route with local information? The second and third questions are not settled by the construction rule alone.^[1]^[3]^[4]

Diagnostic: Is “nearest” measured along the cone bisector, and is the claimed ratio about an existing shortest path or a specified routing algorithm?

Knowledge Transfer¶

A network supplies vertices and connections; routing concerns how paths are found. The portable pattern is controlled sparsification while approximately preserving a metric. Yet the named method depends on Euclidean embedding, angular sectors and projection order; it is not a generic graph sparsifier. A Θ₆ spanner theorem can inform path infrastructure, but importing it into radio-range-limited communication graphs without proving the restricted edges exist is not valid transfer.^[1]^[3]

Examples¶

Θ₆ and half-Θ₆: 2-spanner theorem¶

Bonichon and coauthors define projected-nearest cones on finite planar point sets and identify half-Θ₆ with a triangular-distance Delaunay graph. Since the full Θ₆ contains the relevant 2-spanning subgraph, its shortest-path length between any two input points is at most twice their direct distance under the paper's conditions. This is a proved geometric theorem, not an experiment on an actual wireless deployment.^[1]

Mapped back: points = finite planar S; sectors = six equal cones; selection = least bisector projection; edge union = full Θ₆; metric test = shortest Euclidean-length path ≤2 times direct distance; boundary = general-position/graph-variant assumptions.

Θ₅: spanner does not imply short naive routing¶

Bose and coauthors prove Θ₅ has finite stretch ≤√(50+22√5), with a constructed lower bound. They also construct cases in which traditional forwarding along the edge selected in the cone containing the destination takes very long paths, even though the graph contains a short one. The edge selector still makes a Θ-graph; what fails is the unqualified routing promise.^[3]

Mapped back: points = finite planar configuration; sectors = five cones; selection = projected nearest; path metric = finite graph stretch; routing boundary = a naive online path need not realize the short existing path.

Projected nearest versus Euclidean nearest¶

Construct an apex p=(0,0) and a cone centered on the positive x-axis with half-angle 30°. Let a=(2,0) and b=(1.9,0.9), both inside it. The bisector projections are 2 and 1.9, so Θ selects b, but Euclidean distances are 2 and about 2.10, so Yao selects a. These coordinates are an illustrative calculation, not a source-reported experiment.^[2]

Mapped back: same points and cone; change only the candidate-ranking role; graph identity changes.

Structural Tensions¶

Edge sparsity versus distance stretch. Choosing one edge per cone bounds local outgoing selections independent of n. Coarse cone partitions can leave longer detours; refining the angular partition permits better geometric control but increases the potential edge budget. Exact bounds are k- and variant-specific: Θ₅ and Θ₆ show distinct guarantees, not a smooth universal formula at every k. Diagnostic: What edge budget and proven stretch are required for the actual chosen k?^[1]^[3]

Global short-path existence versus local routing knowledge. A spanner theorem says an appropriate path exists, but an online router with only local graph information may not identify it. More routing state or a tailored algorithm can improve route guarantees, with computational/knowledge costs. Θ₅'s traditional-routing counterexample and the Θ₆ routing study make the distinction concrete. Diagnostic: Is the claim about the graph metric or the path produced by a specified algorithm?^[3]^[4]

Structural–Framed Character¶

This entry is predominantly structural and algorithmic: finite points, cones, projections and selected edges suffice to identify it. Its evaluative weight—“good” stretch, “efficient” routing—depends on application goals, k and graph variant, not on the bare construction. Human designers choose cone orientation and tie rules; computational-geometry research proves theorems under general-position and graph-model conventions. The term's institutional origin is spanner research; calling a radio network a Θ-graph is justified only if the actual link-selection rule and feasible edges match. The vocabulary of “spanning” travels from shortest-path approximation to routing, but a metric existence theorem cannot simply be imported as a local-routing guarantee. Recognizing Θ₅ and Θ₆ as one construction family is sound; importing the Θ₆ factor-2 bound to Θ₅ or to the unrelated three-path theta graph is not. Its character: a sparse geometric graph defined by directional projection choices, with performance guarantees that depend sharply on cone count, variant and path-finding model.^[1]^[3]^[4]

Structural Core vs. Domain Accent¶

The portable skeleton is budgeted local selection that can preserve a global distance relation; routing concerns path discovery. The domain-bound mechanism is a Euclidean point embedding, equal-angle cones, bisector projection ranking and k-dependent stretch proof. A general network need not have angles, and a generic sparse graph need not approximate geometric distance.

A Θ-graph is a geometric network built by a local selection rule. Routing is a related but separate process that may use its edges.

Neighborhood in Abstraction Space¶

Theta Graph sits in a moderately populated region (57^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (48 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-31

Not to Be Confused With¶

Yao graph: Euclidean-nearest instead of projection-nearest in each cone. Half-Θ₆: uses alternating cones and is a particular subgraph with its own theorem. Directed Θ-graph: keeps selected arcs; an undirected union can have different routing properties. Three-path theta graph: a graph-topology shape unrelated to this geometric spanner identity. Wireless link graph: constrained by range/interference, not automatically the complete Euclidean input assumed in cited theorems.^[1]^[2]^[4]

References¶

[1] Bonichon, Nicolas, Cyril Gavoille, Nicolas Hanusse, and David Ilcinkas (2010). “Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces”, definitions and Θ₆ 2-spanner corollary; published conference version doi:10.1007/978-3-642-16926-7_25. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p

[2] Aichholzer, Oswin, et al. (2014). “Theta-3 is connected”, Computational Geometry 47, 910–917, doi:10.1016/j.comgeo.2014.05.001; original article (also reprinted in 2015). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[3] Bose, Prosenjit, Pat Morin, André van Renssen, and Sander Verdonschot (2015). “The Θ₅-graph is a spanner”, Computational Geometry 48, 108–119, doi:10.1016/j.comgeo.2014.08.005; original preprint §5 routing lower bound. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m

[4] Bose, Prosenjit, Jean-Lou De Carufel, and Olivier Devillers (2019). “Expected Complexity of Routing in Θ₆ and Half-Θ₆ Graphs”, arXiv:1910.14289, online-routing analysis; published journal version doi:10.20382/jocg.v11i1a9. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g