Topological information are the most important kind of qualitative spatial information. Current formalisms for the topological aspect of space focus on relations between regions or properties of regions. This work provides a qualitative model for representing the topological internal structure of complex regions, which could be of multiple pieces and or have holes and islands to any finite level. We propose a layered graph model for representing the internal structure of complex plane regions, where each node represents the closure of a connected component of the interior or the exterior of a complex region. The model provides a complete representation in the sense that the (global) nine-intersections between the interiors, the boundaries, and the exteriors of two complex regions can be determined by the (local) RCC8 topological relations between the associated simple regions. Moreover, this graph model has an inherent hierarchy which could be exploited for map generalization.
@cite_3 actually proposed two definitions of simple regions with holes, both requiring that the region have connected interior. The first definition further requires that the boundaries of different exterior components should be disjoint. While this constraint is relaxed in the second definition, it allows spikes in the exterior of such a region. Figure shows such an example. The region' @math in the left of this figure has a spike (i.e. the common boundary of @math and @math ) in the exterior of @math , but its interior @math (showing in the right of this figure) is one-piece.
@cite_3
5053679 2951895579 2508758617 2128738155
The 4-intersection, a model for the representation of topological relations between 2-dimensional objects with connected boundaries and connected interiors, is extended to cover topological relations between 2-dimensional objects with arbitrary holes, called regions with holes. Each region with holes is represented by its generalized region—the union of the object and its holes — and the closure of each hole. The topological relation between two regions with holes, A and B, is described by the set of all individual topological relations between (1) A ’s generalized region and B’s generalized region, (2) A ’s generalized region and each of B’s holes, (3) B’s generalized region with each of A ’s holes, and (4) each of A ’s holes with each of B’s holes. As a side product, the same formalism applies to the description of topological relations between 1-spheres. An algorithm is developed that minimizes the number of individual topological relations necessary to describe a configuration completely. This model of representing complex topological relations is suitable for a multi-level treatment of topological relations, at the least detailed level of which the relation between the generalized regions prevails. It is shown how this model applies to the assessment of consistency in multiple representations when, at a coarser level of less detail, regions are generalized by dropping holes. We consider the non-crossing connectors problem, which is stated as follows: Given n simply connected regions R_1,...,R_n in the plane and finite point sets P_i subset of R_i for i=1,...,n, are there non-crossing connectors y_i for (R_i,P_i), i.e., arc-connected sets y_i with P_i subset of y_i subset of R_i for every i=1,...,n, such that y_i and y_j are disjoint for all i different from j? We prove that non-crossing connectors do always exist if the regions form a collection of pseudo-disks, i.e., the boundaries of every pair of regions intersect at most twice. We provide a simple polynomial-time algorithm if the regions are axis-aligned rectangles. Finally we prove that the general problem is NP-complete, even if the regions are convex, the boundaries of every pair of regions intersect at most four times and P_i consists of only two points on the boundary of R_i for i=1,...,n. Finite convex geometries are combinatorial structures. It follows from a recent result of M. Richter and L.G. Rogers that there is an infinite set @math of planar convex polygons such that @math with respect to geometric convex hulls is a locally convex geometry and every finite convex geometry can be represented by restricting the structure of @math to a finite subset in a natural way. An @math is a differentiable convex simple closed curve @math in the plane having an inscribed circle of radius @math and a circumscribed circle of radius @math such that the ratio @math is at least @math . Motivated by Richter and Rogers' result, we construct a set @math such that (1) @math contains all points of the plane as degenerate singleton circles and all of its non-singleton members are differentiable convex simple closed planar curves; (2) @math with respect to the geometric convex hull operator is a locally convex geometry; (3) as opposed to @math , @math is closed with respect to non-degenerate affine transformations; and (4) for every (small) positive @math and for every finite convex geometry, there are continuum many pairwise affine-disjoint finite subsets @math of @math such that each @math consists of almost-circles of accuracy @math and the convex geometry in question is represented by restricting the convex hull operator to @math . The affine-disjointness of @math and @math means that, in addition to @math , even @math is disjoint from @math for every non-degenerate affine transformation @math . We look at a model of random graphs suggested by Gilbert: given an integer @math and @math , scatter @math vertices independently and uniformly on a metric space, and then add edges connecting pairs of vertices of distance less than @math apart.We consider the asymptotics when the metric space is the interval [0, 1], and @math is a function of @math , for @math . We prove that every upwards closed property of (ordered) graphs has at least a weak threshold in this model on this metric space. (But we do find a metric space on which some upwards closed properties do not even have weak thresholds in this model.) We also prove that every upwards closed property with a threshold much above connectivity's threshold has a strong threshold. (But we also find a sequence of upwards closed properties with lower thresholds that are strictly weak.)