A unified approach to geometric problems using dual cone transformation:

Abstract

This paper uses a new transformation technique that allows a unified treatment to a number of geometric problems. In particular, we are able to offer an optimal algorithm for range query and point enclosure problems. More specifically, we discuss how our approach yields efficient algorithms to the following three classical problems in computational geometry: (1) Given a collection of d-rectangles in E ^d , how many of them intersect an arbitrary query rectangle. (2) Give a collection of rectangles which of them contain an arbitrary query point. (3) Given a set of n points in R ^d and a query d-range q, report the points of S that lie within q. All these results represent significant improvements over the best methods previously known.

Keywords:

• Rectangle intersection
• point enclosure
• orthogonal range query
• dual cone
• geometric transform
• spherically convex
• spherical cap