Let S be a point set in the plane, and let 𝒫(S) and 𝒞(S) be the sets of all plane spanning paths and caterpillars on S. We study reconfiguration operations on 𝒫(S) and 𝒞(S). In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when S is in convex position. If S is in general position, we show that the rotation, compatible flip and flip graphs of 𝒞(S) are connected while the slide graph is sometimes disconnected, but always has a component of size 1/4(3ⁿ-1). We then study sizes of connected components in reconfiguration graphs of plane spanning paths. In this direction, we show that no component of size at most 7 can exist in the flip graph on 𝒫(S).

The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. A BNN representation of function f is a pair (P,N) of sets of Boolean vectors (called positive and negative prototypes) where f(x) = 1 for every positive prototype x ∈ P, f(x) = 0 for every negative prototype x ∈ N, and the value f(x) for x not in (P ∪ N) is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.