Lesson plan
Point location
The point location class of problems is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). In one of its general forms, the problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies. For example, the problem of determining which window of a graphical user interface contains a given mouse click can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window, although specialized data structures may be more appropriate than general-purpose point location data structures in this application. A special case is the point in polygon problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single polygon. Other special cases exist. The problem may be stated for a set of arbitrary regions in space, not necessarily disjoint and not necessarily constituting a partition. Further, one may need to determine the location of several points with respect to the same partition of the space. Or, alternatively, partitions may be changing. In the latter case the class of problems overlaps with range search problems.…
Article summary
The point location class of problems is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). In one of its general forms, the problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies. For example, the problem of determining which window of a graphical user interface contains a given mouse click can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window, although specialized data structures may be more appropriate than general-purpose point location data structures in this application. A special case is the point in polygon problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single polygon. Other special cases exist. The problem may be stated for a set of arbitrary regions in space, not necessarily disjoint and not necessarily constituting a partition. Further, one may need to determine the location of several points with respect to the same partition of the space. Or, alternatively, partitions may be changing. In the latter case the class of problems overlaps with range search problems.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.