article Free Access Share on The Logical Complexity of Geometric Properties in the Plane Author: Louis Hodes Department of Health, Education and Welfare, Division of Computer Research and Technology, National Institue of Health, Public Health Service, Bethesda, Maryland Department of Health, Education and Welfare, Division of Computer Research and Technology, National Institue of Health, Public Health Service, Bethesda, MarylandView Profile Authors Info & Claims Journal of the ACMVolume 17Issue 2pp 339–347https://doi.org/10.1145/321574.321587Published:01 April 1970Publication History 12citation271DownloadsMetricsTotal Citations12Total Downloads271Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper studies the logical complexity of geometric properties in the plane. These properties are characterized according to the length of formulas necessary to express them. In this study a portion of the plane X will be considered as a collection of squares {x1, ..., xn} arranged into a fine grid. A pattern P is a subset of X and the grid is assumed to be fine enough so that approximations to geometrical figures can be obtained. P can be defined by mapping m: X →{0,1} where for x ε X, m(x) = 1 iff x ε P. A set of patterns or a geometrical property ℘ can be expressed as a Boolean function f on the n variables x1, ..., xn such that the value of f is 1 under the assignment m iff P ε ℘.