Title: Trading Time for Space: an O(1) Average time Algorithm for Point-in-Polygon Location Problem. Theoretical Fiction or Practical Usage?
Authors: Skala, Václav
Citation: Machine Graphics and Vision. 1996, vol. 5, no. 3, p. 483-494.
Issue Date: 1996
Document type: preprint
URI: http://hdl.handle.net/11025/11815
ISSN: 1230-0535
Keywords: struktura dat;složitost algoritmů;geometrie
Keywords in different language: data structure;algorithm complexity;geometry
Abstract: Algorithms for Point in polygon problem solution are very often used especially in computer graphics applications The naive implementation has O(N) processing time complexity or O(lg N) complexity if a convex polygon is considered . A new algorithm of O(l) processing complexity was developed . The important feature of the algorithm is that preprocessing complexity is O (N) and memory requirements depend on geometrical properties of the given polygon Usage of the algorithm is expected in applications where many points are tested whether resides in the given polygon or not. The presented approach can be considered as alternative to the parallel processing usage. Experimental results are included, too.
Appears in Collections:Preprinty / Preprints (KIV)

Files in This Item:
File Description SizeFormat 
Skala_1996_POINT-IN.pdfPlný text796,78 kBAdobe PDFView/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/11815

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.