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[25]. 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