Introduction

Consider a database whose entries have multiple searchable attributes. Perhaps a personnel database that stores employees' names, addresses, salaries and dates of birth, or a map that stores the population and location of cities, or a mesh that stores the Cartesian locations of points. In database terminology, the entries are called records and the attributes are called keys. A collection of records is a file. If there are K keys then one can identify each key with a coordinate direction in Cartesian space. Then each record represents a point in K-dimensional space. Searching a file for records whose keys satisfy certain criteria is a query. A query for which the keys must lie in specified ranges is called an orthogonal range query. This is because each of the ranges correspond to intervals in orthogonal directions. The records which satisfy the criteria lie in a box in K-dimensional space. The process of finding these records is called range searching. For example, one could search for cities which lie between certain coordinates longitude and latitude and have populations between 10,000 and 100,000. This orthogonal range query is depicted in the figure below. The box is projected onto the three coordinate planes.

An orthogonal range query for cities.

Example Application: CPT on an Irregular Mesh

Many query problems can be aided by using orthogonal range queries. Consider a file which holds points in 3-D space. Suppose we wish to find the points which lie inside a polyhedron. The brute force approach would be to check each point to see if it is inside. An efficient algorithm would make a bounding box around the polyhedron. To check if a point is inside the polyhedron, one would first check that it is inside the bounding box since that is a much simpler test. In this way one could rule out most of the points before doing the complicated test to see which points are inside the polyhedron. A better approach (for most scenarios) would be to do an orthogonal range query to determine which points lie inside the bounding box. Then one could do the more detailed check on those points. (More generally, one could compute a set of boxes that together contain the polyhedron. This would be more efficient if the volume of the bounding box were much greater than the volume of the polyhedron.)

Consider computing the closest point transform presented in cpt not on the points of a regular grid, but on the points of an irregular mesh (perhaps the vertices of a tetrahedral mesh). To do this one would have to do polyhedron scan conversion for these irregularly spaced points. That is, given a characteristic polyhedron of a face, edge or vertex, we must determine which mesh points are inside. This can be implemented efficiently using orthogonal range queries.

Example Application: Contact Detection

In this section we consider the finite deformation contact problem for finite element meshes. A detailed account of this problem is given in On the formulation and numerical treatment of finite deformation frictional contact problems. We will follow the treatment in A parallel contact detection algorithm for transient solid dynamics simulations using PRONTO3D. Consider a finite element tetrahedron mesh modeling an object (or objects). The boundary of this mesh is a triangle mesh that comprises the surface of the object. The vertices on the surface are called contact nodes and the triangle faces on the surface are called contact surfaces. During the course of a simulation the object may come in contact with itself or other objects. Unless restoring forces are applied on the boundary, the objects will inter-penetrate. In order to prevent this, the contact constraint is applied at the contact nodes. Contact forces are applied to those nodes that have penetrated contact surfaces. Below is an outline of a time step in the simulation.

1. Define the contact surface.
2. Predict the location of nodes assuming no contacts by integrating the equations of motion.
3. Search for potential contacts between nodes and surfaces.
4. Perform a detailed contact check on the potential contacts.
5. Enforce the contacts by applying forces to remove the overlap.

The contact search in the third step is the most time consuming part of the contact detection algorithm. At each time step, each triangle face on the surface is displaced. Nodes which are close to volumes swept out by this motion could potentially contact the surface. One can find these nodes with the following three steps. 1) Compute a bounding box around the two positions (the position at the beginning of the time step and the predicted position at the end of the time step) of the contact surface. 2) Enlarge the bounding box to account for motion of the nodes. This is called the capture box. 3) Perform an orthogonal range query on the surface nodes to find those in the capture box. The contact search is depicted the figure below.

Contact search for a face. The orthogonal range query returns the nodes in the capture box.

Following the contact search, the detailed contact check, step 4, is performed on the potential contacts. In this step, contact is detected by determining if the node penetrates the contact surface during the time step. This is depicted below.

The contact check for a single contact surface and node. The node penetrates the face.

Since the contact search is the most time consuming part of contact detection, the performance of the algorithm depends heavily on efficient methods for doing orthogonal range queries. The contact detection problem has more structure than many orthogonal range query problems. Firstly, there are many range queries. Since there is a query for every face, the number of orthogonal range queries is of the same order as the number of nodes. Secondly, the problem is dynamic. At each time step, the nodes and faces move a small amount. From one time step to the next, the nodes and ranges are slightly different.

We will first consider the problem of doing a single range query, noting which methods are easily adapted to dynamic problems. For this we will collect and compare previously developed algorithms and data structures. Then we will consider the problem of performing a set of orthogonal range queries. The multiple query problem has not previously been studied.