ในเรขาคณิตเชิงคำนวณกราฟธีตาหรือกราฟ -graph เป็น สแปนเนอร์ทางเรขาคณิตประเภทหนึ่งที่คล้ายกับกราฟเหยาวิธีการสร้างพื้นฐานเกี่ยวข้องกับการแบ่งพื้นที่รอบจุดยอดแต่ละจุดออกเป็นชุดของกรวยซึ่งกรวยเหล่านี้จะแบ่งจุดยอดที่เหลือของกราฟออกเป็นส่วนๆ เช่นเดียวกับกราฟเหยา กราฟ-graph จะมีขอบอย่างมากที่สุดหนึ่งขอบต่อกรวย ความแตกต่างอยู่ที่วิธีการเลือกขอบนั้น ในขณะที่กราฟเหยาจะเลือกจุดยอดที่ใกล้ที่สุดตามปริภูมิเมตริกของกราฟ กราฟ-graph จะกำหนดรังสีคงที่ที่อยู่ภายในกรวยแต่ละอัน (โดยทั่วไปคือเส้นแบ่งครึ่งกรวย) และเลือกเพื่อนบ้านที่ใกล้ที่สุดโดยสัมพันธ์กับการฉายภาพตั้งฉากกับรังสีนั้น กราฟที่ได้จะมีคุณสมบัติสแปนเนอร์ที่ดีหลายประการ^{[ 1 ]}${\displaystyle \Theta }$${\displaystyle \Theta }$${\displaystyle \Theta }$

${\displaystyle \Theta }$-กราฟได้รับการอธิบายครั้งแรกโดย Clarkson ^{[ 2 ]}ในปี 1987 และโดยอิสระโดย Keil ^{[ 3 ]}ในปี 1988

${\displaystyle \Theta }$กราฟแบบ π ถูกกำหนดด้วยพารามิเตอร์ไม่กี่ตัวที่กำหนดโครงสร้างของมัน พารามิเตอร์ที่เห็นได้ชัดที่สุดคือφ ซึ่งสอดคล้องกับจำนวนกรวยมุมเท่ากันที่แบ่งพื้นที่รอบจุดยอดแต่ละจุด โดยเฉพาะอย่างยิ่ง สำหรับจุดยอด π กรวยรอบ π สามารถจินตนาการได้ว่าเป็นรังสีอนันต์สองเส้นที่แผ่ออกมาจากจุดยอดนั้น โดยมีมุมระหว่างกัน เมื่อเทียบกับπ เราสามารถกำหนดชื่อกรวยเหล่านี้เป็น φ ผ่าน φ ในรูปแบบทวนเข็มนาฬิกาจากφ ซึ่งโดยทั่วไปจะเปิดเพื่อให้เส้นแบ่งครึ่งมุมมีมุม 0 เมื่อเทียบกับระนาบ เนื่องจากกรวยเหล่านี้แบ่งระนาบ พวกมันจึงแบ่งเซตจุดยอดที่เหลือของกราฟ (โดยสมมติตำแหน่งทั่วไป φ ) ออกเป็นเซต φ ผ่านφ อีกครั้งเมื่อเทียบกับφ จุดยอดทุกจุดในกราฟจะได้รับจำนวนกรวยเท่ากันในทิศทางเดียวกัน และเราสามารถพิจารณาเซตของจุดยอดที่ตกอยู่ในแต่ละ φ ได้ ${\displaystyle k}$${\displaystyle p}$${\displaystyle p}$${\displaystyle \theta =2\pi /k}$${\displaystyle p}$${\displaystyle C_{1}}$${\displaystyle C_{k}}$${\displaystyle C_{1}}$${\displaystyle V_{1}}$${\displaystyle V_{k}}$${\displaystyle p}$

เมื่อพิจารณากรวยเดี่ยว เราจำเป็นต้องระบุรังสีอีกเส้นหนึ่งที่แผ่ออกมาจากซึ่งเราจะติดป้ายกำกับว่า สำหรับทุกจุดยอดในเราจะพิจารณาการฉายภาพเชิงตั้งฉากของแต่ละจุดยอดลงบนสมมติว่าเป็นจุดยอดที่มีการฉายภาพดังกล่าวใกล้ที่สุด จากนั้นขอบจะถูกเพิ่มเข้าไปในกราฟ นี่คือความแตกต่างหลักจากกราฟ Yao ซึ่งจะเลือกจุดยอดที่ใกล้ที่สุดเสมอ ในภาพตัวอย่าง กราฟ Yao จะรวมขอบแทน ${\displaystyle p}$${\displaystyle l}$${\displaystyle V_{i}}$${\displaystyle v\in V_{i}}$${\displaystyle l}$${\displaystyle r}$${\displaystyle \{p,r\}}$${\displaystyle \{p,q\}}$

การสร้างกราฟ- สามารถทำได้ด้วยอัลกอริทึม sweeplineในเวลา^{[ 1 ]}${\displaystyle \Theta }$${\displaystyle O(n\log {n})}$

${\displaystyle \Theta }$-กราฟแสดงคุณสมบัติ เชิงเรขาคณิตที่ เป็นประโยชน์หลายประการ

เมื่อพารามิเตอร์เป็นค่าคงที่กราฟ -graph จะเป็น sparse spanner เนื่องจากแต่ละกรวยสร้างขอบได้มากที่สุดหนึ่งขอบต่อกรวย ดังนั้นจุดยอดส่วนใหญ่จะมีดีกรีน้อย และกราฟโดยรวมจะมีขอบ มากที่สุด${\displaystyle k}$${\displaystyle \Theta }$${\displaystyle k\cdot n=O(n)}$

ปัจจัยการยืดระหว่างจุดสองจุดใดๆ ในสแปนเนอร์ถูกกำหนดให้เป็นอัตราส่วนระหว่างระยะทางในปริภูมิเมตริกและระยะทางภายในสแปนเนอร์ (เช่น จากขอบที่ตามมาของสแปนเนอร์) ปัจจัยการยืดของสแปนเนอร์ทั้งหมดคือปัจจัยการยืดสูงสุดเหนือจุดสองจุดทั้งหมดภายในนั้น โปรดจำจากข้างต้นว่าเมื่อกราฟ จะมีปัจจัยการยืด ไม่เกิน^{[ 1 ]} หาก เลือกเส้นฉายตั้งฉาก ในแต่ละกรวยเป็นเส้นแบ่งครึ่งมุมแล้ว สำหรับ อัตราส่วนการแผ่ขยายจะไม่เกิน^{[ 4 ]}${\displaystyle \theta =2\pi /k}$${\displaystyle k\geq 9}$${\displaystyle \Theta }$${\displaystyle 1/(\cos \theta -\sin \theta )}$${\displaystyle l}$${\displaystyle k\geq 7}$${\displaystyle 1/(1-2\sin(\pi /k))}$

สำหรับกราฟจะสร้างกราฟเพื่อนบ้านที่ใกล้ที่สุดสำหรับจะเห็นได้ง่ายว่ากราฟเชื่อมต่อกัน เนื่องจากแต่ละจุดยอดจะเชื่อมต่อกับบางสิ่งทางซ้ายและบางสิ่งทางขวา หากมีอยู่ สำหรับ^{[ 5 ]} , ^{[ 6 ]} , ^{[ 7 ]} , ^{[ 8 ]}และ, ^{[ 4 ]}กราฟเป็นที่ทราบกันว่าเชื่อมต่อกัน ผลลัพธ์เหล่านี้จำนวนมากยังให้ขอบเขตบนและ/หรือล่างของอัตราส่วนการแผ่ขยายอีกด้วย ${\displaystyle k=1}$${\displaystyle \Theta }$${\displaystyle k=2}$${\displaystyle k=3}$${\displaystyle 4}$${\displaystyle 5}$${\displaystyle 6}$${\displaystyle \geq 7}$${\displaystyle \Theta }$

เมื่อเป็นจำนวนคู่เราสามารถสร้างรูปแบบหนึ่งของกราฟที่เรียกว่ากราฟครึ่งซึ่งกรวยจะถูกแบ่งออกเป็น เซต คู่และ เซต คี่สลับกันไป และขอบจะถูกพิจารณาเฉพาะในกรวยคู่ (หรือเฉพาะกรวยคี่) กราฟครึ่งมีคุณสมบัติที่ดีบางอย่าง ตัวอย่างเช่นกราฟครึ่ง (และด้วยเหตุนี้กราฟ ซึ่งเป็นการรวมกันของกราฟครึ่งสองกราฟที่เสริมกัน) เป็นที่ทราบกันว่าเป็น 2-spanner ^{[ 8 ]}${\displaystyle k}$${\displaystyle \Theta _{k}}$${\displaystyle \Theta _{k}}$${\displaystyle \Theta _{k}}$${\displaystyle \Theta _{6}}$${\displaystyle \Theta _{6}}$${\displaystyle \Theta _{6}}$

• เครื่องมือที่เขียนด้วยภาษาจาวา
• เครื่องมือ Spanners แบบใช้รูปทรงกรวยในไลบรารีอัลกอริธึมเรขาคณิตเชิงคำนวณ (CGAL)

• กราฟเหยา
• กราฟเซมิเหยา
• ประแจเรขาคณิต