Week 3: Top data struct: plane sub/motivations

Question 1

Topological data structures for plane subdivisions

Answer 1

1) Connectivity info incorporated in data structures for plane subdivision by storing explicitly a subset of the 9 relations
2) Two types of points:
- points that are endpoints of a line (vertices)
- points that define the shape (geometry) of a line
3) For polygons/lines:
- adjacency info. e.g. encode polygons on each side of a boundary line (EF relation)
4) In a plane subdivision: only topological relation meet (connectivity along the boundary). Entities can only be connected by sharing a portion of their boundary e.g. two lines by sharing portion of their boundary e.g. two lines by sharing an endpoint, two polygons by sharing a line (adjacent)

Question 2

Topological data structures: motivations

Answer 2

1) Storing connectivity info explicitly allows for more efficient spatial queries
2) Topology is an important criterion to establish the correctness (integrity, consistency) of geographic databases