A set of vectors S ⊆ R d is ( k 1 , ε ) -clusterable if there are k 1 balls of radius ε that cover S . A set of vectors S ⊆ R d is ( k 2 , δ ) -far from being clusterable if there are at least k 2 vectors in S , with all pairwise distances at least δ . We propose a probabilistic algorithm to distinguish between these two cases. Our algorithm reaches a decision by only looking at the extreme values of a scalar valued hash function, defined by a random field , on S ; hence, it is especially suitable in distributed and online settings. An important feature of our method is that the algorithm is oblivious to the number of vectors: in the online setting, for example, the algorithm stores only a constant number of scalars, which is independent of the stream length. We introduce random field hash functions, which are a key ingredient in our paradigm. Random field hash functions generalize locality-sensitive hashing (LSH). In addition to the LSH requirement that “nearby vectors are hashed to similar values”, our hash function also guarantees that the “hash values are (nearly) independent random variables for distant vectors”. We formulate necessary conditions for the kernels which define the random fields applied to our problem, as well as a measure of kernel optimality, for which we provide a bound. Then, we propose a method to construct kernels which approximate the optimal one.

Collision-avoiding motion planning for articulated robotic arms is one of the major challenges in robotics. The difficulty of the problem arises from its high dimensionality and the intricate geometry of the feasible space. Our goal is to seek large convex domains in configuration space, which contain no obstacles. In these domains, simple linear trajectories are guaranteed to be collision free, and can be leveraged for further optimization. To find such domains, practitioners have harnessed a methodology known as Sum-Of-Squares (SOS) Programming. SOS programs, however, are notorious for their poor scaling properties, which makes it challenging to employ them for complex problems. In this paper, we explore a simple formulation for a two-dimensional arm, which results in smaller SOS programs than previous suggested ones. We show that this formulation can express a variety of scenarios in a unified manner.