Algorithms and Data Structures Book

	Lower Bounds to Processor-Time Tradeoffs Under Bounded Speed Message Propagation	1
	The Two-Line Center Problem from a Polar View: a New Algorithm and Data Structure	13
	On some Geometric Selection and Optimization Problems via Sorted Matrices	26
	Load Balancing in Quorum Systems	38
	Balanced Distributed Search Trees Do Not Exist	50
	Two-Floodlight Illumination of Convex Polygons	62
	On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra	74
	Scheduling Jobs that Arrive Over Time	86
	Dynamic Algorithms for the Dyck Languages	98
	Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications	109
	Computing a Shortest Watchman Path in a Simple Polygon in Polynomial Time	122
	Going Home Through an Unknown Street	135
	Page Migration with Limited Local Memory Capacity	147
	Randomized Algorithms for Metrical Task Systems	159
	Efficient Geometric Algorithms for Workpiece Orientation in 4- and 5 Axis NC Machining	171
	Computing Common Tangents Without a Separating Line	183
	Online Perfect Matching and Mobile Computing	194
	Competitive Algorithms for the On-line Traveling Salesman	206
	Quadrangulations of Planar Sets	218
	A Linear-time Construction of the Relative Neighborhood Graph within a Histogram	228
	Computing Proximity Drawings of Trees in the 3-Dimensional Space	239
	Routing on Trees via Matchings	251
	A Ranking Algorithm for Hamilton Paths in Shuffle-Exchange Graphs	263
	Amortization Results for Chromatic Search Trees, with an Application to Priority Queues	270
	Fast Meldable Priority Queues	282
	On the Computation of Fast Data Transmissions in Networks with Capacities and Delays	291
	Routing with Delays when Storage is Costly	303
	Algorithmic Arguments in Physics of Computation	315
	The Buffer Tree: A New Technique for Optimal I/O-Algorithms	334
	Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep	346
	Computing a Dominating Pair in an Asteroidal Triple-free Graph in Linear Time	358
	A Linear Algorithm for the Maximal Planar Subgraph Problem	369
	Topology B-Trees and their Applications	381
	In-Place Calculation of Minimum-Redundancy Codes	393
	Regular-Factors in the Complements of Partial k-Trees	403
	Obstructions to Within a Few Vertices or Edges of Acyclic	415
	Faster Enumeration of All Spanning Trees of a Directed Graph	428
	A Simpler Minimum Spanning Tree Verification Algorithm	440
	On Approximation Properties of the Independent Set Problem in Degree 3 Graphs	449
	Approximation of Constraint Satisfaction via Local Search	461
	On the Difficulty of Range Searching	473
	Tables Should Be Sorted (on random access machines)	482
	Improved Length Bounds for the Shortest Superstring Problem	494
	Non-Overlapping Local Alignments	506
	Experiences with the Implementation of Geometric Algorithms	518
	Author Index	519