     Next: Basic Data Types for Up: Advanced Data Types for Previous: Sets of Parallel Rational   Contents   Index

# Planar Subdivisions ( subdivision )

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.

#include < LEDA/geo/subdivision.h >

Creation

 subdivision S(GRAPH& G) creates an instance S of type subdivision 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. const I& S.inf(face f) returns the information of face f. face S.locate_point(point p) returns the face containing point p. face S.outer_face() returns the outer face of S.

Implementation

Planar subdivisions are implemented by parameterized planar maps and an additional data structure for point location based on partially persistent search trees. Operations position and inf take constant time, a locate_point operation takes (expected) time O(log n). Here n is the number of nodes. The space requirement is O(n + m) and the initialization time is O(n + m log m), where m is the number of edges in the map.     Next: Basic Data Types for Up: Advanced Data Types for Previous: Sets of Parallel Rational   Contents   Index