withinDistance

Within distance is a term used to describe a proximity relation between two geometric objects or points, defined by whether their separation does not exceed a specified threshold. It is widely employed in mathematics, computer science, and geographic information systems to express the idea that objects are close to each other within a given radius or distance.

Formal definition: In a metric space with distance function d, two objects A and B are within distance ε if d(A, B) ≤ ε. For simple Euclidean geometry, d is the Euclidean distance. For extended objects such as lines or polygons, the distance is typically the minimum distance between any point on one object and any point on the other, though alternate distance measures may be used depending on the context (for example Manhattan or Chebyshev metrics).

Computation and indexing: Within-distance queries usually involve distance calculation and pruning to improve efficiency. Spatial indexes such as R-trees or k-d trees accelerate these queries by filtering candidates using bounding volumes before computing exact distances. In practice, a two-stage approach is common: first filter with a bounding box or envelope, then confirm with an exact distance computation for the remaining candidates.

Applications: This concept underpins clustering algorithms like DBSCAN, proximity alerts, collision avoidance, and nearest-neighbor search. It is also expressed in query languages as predicates such as ST_DWithin in spatial databases, which returns object pairs within a specified distance.

Limitations: The outcome depends on choice of distance metric and threshold ε. Performance varies with data distribution and indexing strategy, and for very large datasets approximate methods may be employed.

See also: proximity query, epsilon-neighborhood, nearest neighbor search, metric space.