This newly expanded and updated second edition of the best-selling classic continues to
take the" mystery" out of designing algorithms, and analyzing their efficacy and efficiency …

The Handbook of Discrete and Computational Geometry is intended as a reference book
fully accessible to nonspecialists as well as specialists, covering all major aspects of both …

A natural and well-studied problem in algorithmic graph theory and network optimization is
that of computing a\shortest path" between two nodes, s and t, in a graph whose edges …

A human observer can effortlessly identify visible portions of geometric objects present in the
environment. However, computations of visible portions of objects from a viewpoint involving …

In this chapter we survey geometric techniques which have been used to measure the
similarity or distance between shapes, as well as to approximate shapes, or interpolate …

We consider the problem of constructing street networks from geo-referenced trajectory data:
Given a set of trajectories in the plane, compute a street network that represents all …

We improve the time complexities for solving the polygonal curve approximation problems
formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n …

It is well-known that inference in graphical models is hard in the worst case, but tractable for
models with bounded treewidth. We ask whether treewidth is the only structural criterion of …

The similarity of two polygonal curves can be measured using the Fréchet distance. We
introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut …

We consider the problem of approximating a polygonal curve P under a given error criterion
by another polygonal curve P'whose vertices are a subset of the vertices of P. The goal is to …