Volume 4 Number 9 (Sep. 2009)
Home > Archive > 2009 > Volume 4 Number 9 (Sep. 2009) >
JCP 2009 Vol.4(9): 913-919 ISSN: 1796-203X
doi: 10.4304/jcp.4.9.913-919

Canonical Polygon Queries on the Plane: A New Approach

S. Sioutas, D. Sofotassios, K. Tsichlas, D. Sotiropoulos, P. Vlamos
Ionian University-Department of Informatics, Computer Technology Institute, Aristotle University of Thessaloniki-Informatics Department, Greece
Abstract—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 axisparallel). We present two new algorithms for this problem. The first one requires O(n log2 n) space and O(k log3n loglogn +A) query time. A simple modification scheme on first algorithm lead us to a second solution, which consumes O(n2) space and O(k 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(n2) 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++.

Index Terms—Algorithms and Complexity, Data Structures, Computational Geometry, Spatial Databases.

[PDF]

Cite: S. Sioutas, D. Sofotassios, K. Tsichlas, D. Sotiropoulos, P. Vlamos, "Canonical Polygon Queries on the Plane: A New Approach," Journal of Computers vol. 4, no. 9, pp. 913-919, 2009.

General Information

ISSN: 1796-203X
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 13, 2018 News!

    Vol 13, No 10 has been published with online version   [Click]

  • Apr 28, 2019 News!

    Vol 14, No 4 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

    Vol 14, No 3 has been published with online version   [Click]

  • Feb 22, 2019 News!

    Vol 14, No 2 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Jan 04, 2019 News!

    Vol 14, No 1 has been published with online version   [Click]

  • Read more>>