Skip to content

Problems News About Submit

← All problems

Minimum-Link Path in 2D

Can a minimum-link path among polygonal obstacles be found in subquadratic time?

Abstract

Determine whether a minimum-link path between two points in a planar polygonal domain can be computed in subquadratic time.

Background and progress

An essentially quadratic algorithm is known for minimum-link paths in polygonal domains [Mitchell et al., 1992]. Whether the quadratic barrier can be broken remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p22.

Reference papers

Minimum-link paths among obstacles in the planeJoseph S. B. Mitchell, Günter Rote, Gerhard J. WoegingerAlgorithmica · 1992

© 2026 OpenTCS · All rights reserved.

Coming soon

Organizer

Boyuan Wang

Minghan Wang

Bochao Li

Hongwei Hu