CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

A Note on Locating a Set of Points in a Planar Subdivision

source

SIAM Journal of Computing. Society for Industrial and Applied Mathematics, November, 1979. vol. 8: pp. 542-545 : ill. includes some bibliographical references

summary

In this note the author shows algorithmically that a set of k points can be located in the planar subdivision induced by straight-line planar graph with n vertices in time O(k log k) + O(n) + O(k log n), given a preprocessing time O(n log n)

keywords

algorithms, computational geometry, point inclusion