Counting slope regions in the surface graphs

Abstract

The discrete version of a continuous surface sampled at optimum sampling rate can be well expressed in form of a neighborhood graph containing the critical points (maxima, minima, saddles) of the surface. Basic operations on the graph such as edge contraction and removal eliminate non-critical points and collapse plateau regions resulting in the formation of a graph pyramid. If the neighborhood graph is well-composed, faces in the graph pyramid are slope regions. In this paper we focus on the graph on the top of the pyramid which will contain critical points only, self-loops and multiple edges connecting the same vertices. We enumerate the different possible configurations of slope regions, forming a catalogue of different configurations when combining slope regions and studying the number of slope regions on the top.