Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes

DOI10.1007/s00454-003-0813-8zbMath1094.68105OpenAlexW2015432477MaRDI QIDQ1889918

Ingo Schurr, Tibor Szabó

Publication date: 13 December 2004

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-003-0813-8

zbMATH Keywords

vertex-oracle model

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (9)

Generation of proper families of functions ⋮ Unique end of potential line ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Counting unique-sink orientations ⋮ Violator spaces: Structure and algorithms ⋮ ONE-TO-ONE CORRESPONDENSE BETWEEN PROPER FAMILIES OF BOOLEAN FUNCTIONS AND UNIQUE SINK ORIENTATIONS OF CUBES ⋮ Random edge can be exponential on abstract cubes ⋮ Unnamed Item ⋮ The complexity of optimization on grids

This page was built for publication: Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes