This paper presents a computational approach to extracting basic perceptual structure, or the lowest level grouping in dot patterns. The goal is to extract the perceptual segments of dots that group together because of their relative locations. The dots are interpreted as belonging to the interior or the border of a perceptual segment, or being along a perceived curve, or being isolated. To perform the lowest level grouping, first the geometric structure of the dot pattern is represented in terms of certain geometric properties of the Voronoi neighborhoods of the dots. The grouping is accomplished through independent modules that possess narrow expertise for recognition of typical interior dots, border dots, curve dots and isolated dots, from the properties of the Voronoi neighborhoods. The results of the modules are allowed to influence and change each other so as to result in perceptual components that satisfy global, Gestalt criteria such as border or curve smoothness and component compactness. Such lateral communication among the modules makes feasible a perceptual interpretation of the local structure in a manner that best meets the global expectations. Thus, an integration is performed of multiple constraints, active at different perceptual levels and having different scopes in the dot pattern, to infer the lowest level perceptual structure. The local interpretations as well as lateral corrections are performed through constraint propagation using a probabilistic relaxation process. The result of the lowest level grouping phase is the partitioning of the dot pattern into different perceptual segments or tokens. Unlike dots, these segments possess size and shape properties in addition to locations which can then be further grouped.