1.6.7 Point Location

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A decomposition of the plane into polygonal regions, and a query point q .

Problem: Which region contains the query point q ?

Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Arrange - maintainance of arrangements with point location (C) (rating 6)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)
  • Joseph O'Rourke's Computational Geometry (C) (rating 3)

    Related Problems

  • Kd-Trees
  • Maintaining Line Arrangements
  • Nearest Neighbor Search
  • Range Search
  • Voronoi Diagrams

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .