This book is primarily a textbook introduction to various areas of discrete geometry. In each
area, it explains several key results and methods, in an accessible and concrete manner. It …

Davenport Schinzel sequences are sequences that do not contain forbidden alternating
subsequences of certain length. They are a powerful combinatorial tool applicable in …

About ten years ago, the eld of range searching, especially simplex range searching, was
wide open. At that time, neither e cient algorithms nor nontrivial lower bounds were known …

A central problem in computational geometry, range searching arises in many applications,
and a variety of geometric problems can be formulated as range-searching problems. A …

In this paper we present a variety of problems in the interface between combinatorics and
geometry around the theorems of Helly, Radon, Carathéodory, and Tverberg. Through these …

Given two planar sets A and B, we examine the problem of determining the smallest ϵ such
that there is a Euclidean motion (rotation and translation) of A that brings each member of A …

The allowable sequence associated to a configuration of points was first developed by the
authors in order to investigate what combinatorial structure lay behind the Erdos-Szekeres …

Used for topology control in ad-hoc wireless networks, Power Assignment is a family of
problems, each defined by a certain connectivity constraint (such as strong connectivity) The …

Line and hyperplane location problems play an important role not only in operations
research and location theory, but also in computational geometry and robust statistics. This …

Recent combinatorial algorithms for linear programming also solve certain non-linear
problems. We call these Generalized Linear Programming, or GLP, problems. One way in …