Credit-based amortized analysis is sound for persistent data structures when credits are stored only on thunks, and Okasaki's debit approach receives a formal operational semantics.
[FL93] Joel Friedman and Nathan Linial
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 3roles
background 1polarities
background 1representative citing papers
Subquadratic Õ(n^{2-1/48}) algorithm for shortest tours of disjoint orthogonal polygons, plus linear-time results for ortho-convex and rectangular cases.
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
citing papers explorer
-
Persistent Amortised Analysis, Operationally
Credit-based amortized analysis is sound for persistent data structures when credits are stored only on thunks, and Okasaki's debit approach receives a formal operational semantics.
-
Touring a Sequence of Orthogonal Polygons
Subquadratic Õ(n^{2-1/48}) algorithm for shortest tours of disjoint orthogonal polygons, plus linear-time results for ortho-convex and rectangular cases.
-
Visibility Queries in Simple Polygons
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.