Canonical polygon Queries on the plane: a New Approach

Details Canonical polygon Queries on the plane: a New Approach Canonical polygon Queries on the plane: a New Approach

2008-05-17

arxiv.org/abs/0805.2681v2

Computer Science

Computational Geometry

7 pages, 9 figures, Accepted for publication in Journal of Computers (JCP), http://www.informatik.uni-trier.de/~ley/db/journal

Scientific paper

The polygon retrieval problem on points is the problem of preprocessing a set of $n$ points on the plane, so that given a polygon query, the subset of points lying inside it can be reported efficiently. It is of great interest in areas such as Computer Graphics, CAD applications, Spatial Databases and GIS developing tasks. In this paper we study the problem of canonical $k$-vertex polygon queries on the plane. A canonical $k$-vertex polygon query always meets the following specific property: a point retrieval query can be transformed into a linear number (with respect to the number of vertices) of point retrievals for orthogonal objects such as rectangles and triangles (throughout this work we call a triangle orthogonal iff two of its edges are axis-parallel). We present two new algorithms for this problem. The first one requires $O(n\log^2{n})$ space and $O(k\frac{log^3n}{loglogn}+A)$ query time. A simple modification scheme on first algorithm lead us to a second solution, which consumes $O(n^2)$ space and $O(k \frac{logn}{loglogn}+A)$ query time, where $A$ denotes the size of the answer and $k$ is the number of vertices. The best previous solution for the general polygon retrieval problem uses $O(n^2)$ space and answers a query in $O(k\log{n}+A)$ time, where $k$ is the number of vertices. It is also very complicated and difficult to be implemented in a standard imperative programming language such as C or C++.

Affiliated with

Also associated with

No associations

Rating

Canonical polygon Queries on the plane: a New Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Canonical polygon Queries on the plane: a New Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Canonical polygon Queries on the plane: a New Approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614667