← All problems

Yao-Yao Graph a Spanner?

For an integer kk, construct the directed Yao graph by retaining the shortest outgoing edge in each of kk equal cones at every point, then retain only the shortest incoming edge per cone and ignore orientations to obtain YYkYY_k. Determine whether, for appropriate fixed kk, there is a constant tt such that YYkYY_k is always a Euclidean tt-spanner.

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li