Text this: Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems