**A random polynomial-time algorithm for approximating the volume of convex bodies**

Martin Dyer, Alan Frieze, Ravi Kannan

Pages: 1-17

DOI: 10.1145/102782.102783

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly...

**The weighted region problem**: finding shortest paths through a weighted planar subdivision

Joseph S. B. Mitchell, Christos H. Papadimitriou

Pages: 18-73

DOI: 10.1145/102782.102784

The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the...

**A fast planar partition algorithm, II**

Kentan Mulmuley

Pages: 74-103

DOI: 10.1145/102782.102785

Randomized, optimal algorithms to find a partition of the plane induced by a set of algebraic segments of a bounded degree, and a set of linear chains of a bounded degree, are given. This paper also provides a new technique for clipping, called...

**Optimal sample cost residues for differential database batch query problems**

Dan E. Willard

Pages: 104-119

DOI: 10.1145/102782.102786

In many computing applications, there are several equivalent algorithms capable of performing a particular task, and no one is the most efficient under all statistical distributions of the data. In such contexts, a good heuristic is to take a...

**Evaluation of queries in independent database schemes**

Yehoshua Sagiv

Pages: 120-161

DOI: 10.1145/102782.102787

A simple characterization of independent database schemes is proved. An algorithm is given for translating a tableau T, posed as a query on a representative instance, to a union of tableaux that is equivalent to...

**Planar graph decomposition and all pairs shortest paths**

Greg N. Frederickson

Pages: 162-204

DOI: 10.1145/102782.102788

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in...

**Extended Horn sets in propositional logic**

V. Chandru, J. N. Hooker

Pages: 205-221

DOI: 10.1145/102782.102789

The class of Horn clause sets in propositional logic is extended to a larger class for which the satisfiability problem can still be solved by unit resolution in linear time. It is shown that to every arborescence there corresponds a family of...

**Upper and lower bounds on switching energy in VLSI**

Gloria Kissin

Pages: 222-254

DOI: 10.1145/102782.102790

A technology-independent framework is established for measuring the
switching energy consumed by very
large scale integrated (VLSI) circuits. Techniques are developed for
analyzing functional energy...