  We focus on the problem of class-agnostic instance segmentation of LiDAR
point clouds. We propose an approach that combines graph-theoretic search with
data-driven learning: it searches over a set of candidate segmentations and
returns one where individual segments score well according to a data-driven
point-based model of "objectness". We prove that if we score a segmentation by
the worst objectness among its individual segments, there is an efficient
algorithm that finds the optimal worst-case segmentation among an exponentially
large number of candidate segmentations. We also present an efficient algorithm
for the average-case. For evaluation, we repurpose KITTI 3D detection as a
segmentation benchmark and empirically demonstrate that our algorithms
significantly outperform past bottom-up segmentation approaches and top-down
object-based algorithms on segmenting point clouds.
