velox only requires a C++11 capable compiler, which shouldn’t be an issue on most contemporary systems. However, velox depends on the rgdal, rgeos, and sf packages, which require the external GDAL (>= 2.0.0), GEOS (>= 3.3.0), PROJ.4 (>= 4.8.0), and UDUNITS libraries. On Ubuntu (>= 14.04), install these dependencies using:
sudo add-apt-repository -y ppa:ubuntugis/ubuntugis-unstable
sudo apt-get update
sudo apt-get install libgdal-dev libproj-dev libgeos-dev libudunits2-dev
See the sf README for information about installation on other platforms.