Optimal algorithms to compute the closure of a set of iso-rectangles
1984; Academic Press; Volume: 5; Issue: 2 Linguagem: Inglês
10.1016/0196-6774(84)90027-0
ISSN1090-2678
AutoresEljas Soisalon-Soininen, Derick Wood,
Tópico(s)Optimization and Search Problems
ResumoThree varieties of the closure of a set of iso-(oriented) rectangles, i.e., rectilin-early-oriented rectangles, are introduced. These are uni-directional, diagonal, and rectangular closure. First a strong decomposition theorem for diagonal closure in terms of uni-directional closure is proved. Then time and space optimal algorithms to compute uni-directional and diagonal closure, each running in O(nlogn) time and O(n) space, are described. An O(nlogn) time and space algorithm for rectangular closure is also described. The algorithm for diagonal closure has applications in database concurrency control: an O(nlogn) time and O(n) space algorithm for testing for safety and detecting deadlocks in locked transaction systems is obtained.
Referência(s)