Skip to content

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 divides directions around each point of a finite planar set into k ≥ 3 equal cones with a shared orientation and selects at most one edge per cone: the candidate whose orthogonal projection onto the cone bisector is nearest to the apex. This differs from a Yao graph, which selects by ordinary Euclidean distance. For fixed k the construction uses at most kn selected arcs, but its path-stretch guarantee depends on k and graph variant.[1][2]

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.

Scope of Application

Bonichon and colleagues proved full Θ₆ is a geometric 2-spanner through its half-Θ₆ subgraph. Bose and colleagues proved Θ₅ is a spanner with a larger upper bound, approximately 9.960. These results concern complete Euclidean planar point sets under mathematical assumptions, not automatic wireless-radio topology guarantees.[1][3]

Clarity

Separate three claims: how the graph is built, whether some short path exists, and whether a specified local routing algorithm finds it. The original Θ₅ paper constructs cases where traditional destination-cone forwarding takes very long paths despite the graph's finite stretch. State directed versus undirected edges, tie rules and the relevant k.[3][4]

Manages Complexity

At most one selection per cone cuts the complete graph's O(n²) possible edges to O(kn) selections. Sparse edges can still support bounded detours for proven variants, but fewer cones and limited routing knowledge can worsen performance. A 2-spanner theorem for Θ₆ does not apply verbatim to Θ₅.[1][3]

Abstract Reasoning

For each apex, draw cones, project candidates onto each bisector and select the minimum projection. Only then test shortest-path stretch or a routing procedure. Sparsity versus stretch and global path existence versus local route finding are separate practical tradeoffs. Do not call a three-internally-disjoint-path graph or a Yao graph this same geometric construction.[2][3]

Knowledge Transfer

A network supplies vertices and connections; routing concerns how paths are found. The reusable idea is sparse local selection preserving a global metric approximately; the Θ identity itself needs Euclidean embedding, angular cones and projection order.[1]

Neighborhood in Abstraction Space

Theta Graph sits in a moderately populated region (57th 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

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

[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

[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

[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 ↩