← All problems

Minimum-Link Path in 2D

Given a polygonal domain in the plane with total complexity nn and two points ss and tt in the domain, find an ss--tt polygonal path contained in the domain with the minimum number of links. Determine whether this can be done in o(n2)o(n^2) worst-case time.

Organizer

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