| Sorting Similar Vectors (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We show how to sort a sequence of k n-bit vectors presented as a list of singlebit changes between consecutive vectors, in O((n + k) log n) deterministic time. An application of this result to a computational problem in arrangements of geometric shapes is presented. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||