Definition
An instance S of the parameterized data type subdivision<I> is a subdivision of the two-dimensional plane, i.e., an embedded planar graph with straight line edges (see also sections Planar Maps and Parameterized Planar Maps). With each node v of S is associated a point, called the position of v and with each face of S is associated an information from data type I, called the information type of S.
Creation
| subdivision<I> | S(GRAPH<point,I>& G); | creates an instance S of type subdivision<I> and initializes it to
the subdivision represented by the parameterized directed graph G.
The node entries of G (of type point) define the positions of the
corresponding nodes of S. Every face f of S is assigned the
information of one of its bounding edges in G.
Precondition: G represents a planar subdivision, i.e., a straight line embedded planar map. |
|
Operations
| point | S.position(node v) | returns the position of node v. |
| I | S.inf(face f) | returns the information of face f. |
| face | S.locate_point(point p) | returns the face containing point p. |
Implementation
Planar subdivisions are implemented by parameterized planar maps and an additional data structure for point location based on persistent search trees [22]. Operations position and inf take constant time, a locate_point operation takes time O(log^2 n). Here n is the number of nodes. The space requirement and the initialization time is O(n^2).