Skip Navigation
Return to Layout View | Home | A-Z Directory | my UMaine | MaineStreet | Campus Map | Calendar
Follow UMaine on Twitter | Join UMaine on Facebook | Watch UMaine on YouTube | Admissions | Parents & Family | Emergency

School of Computing and Information Science

Site Navigation:

The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments

Yohei Kurata and Max J. Egenhofer, The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments, in: M. Raubal, H. Miller, A. Frank, and M. Goodchild (eds.) GIScience 2006—4th International Conference on Geographic Information Science, Lecture Notes in Computer Science, Vol. 4197, pp. 269-286.

Directed line segments are fundamental geometric elements used to model through their spatial relations such concepts as divergence, confluence, and interference. A new model is developed that captures spatial relations between pairs of directed line segments through the intersections of the segments’ heads, bodies, and tails. This head-body-tail intersection identifies 68 classes of topological relations between two directed line segments highlighting two equal-sized subsets of corresponding relations that differ only by their empty and non-empty body-body intersections. The relations’ conceptual neighborhood graph takes the shape of a torus inside a torus, one for each subset. Another 12 classes of topological relations are distinguished if the segments’ exteriors are considered as well, lining up such that their conceptual neighborhood graph forms another torus that contains the other two tori. These conceptual neighborhoods as well as the relations’ composition table enable spatial inferences and similarity assessments in a consistent and reasoned manner.


Contact Information

School of Computing and Information Science
348 Boardman Hall
Orono, ME 04469
Phone: (207) 581-2188 | Fax: (207) 581-2206E-mail:
The University of Maine
Orono, Maine 04469