What does "irregularly spaced spatial data" mean? When I read the paper “Multiscale methods for data on graphs and irregular multidimensional situations”, by Maarten Jansen, Guy P. Nason and B. W. Silverman, I find the term “irregularly spaced spatial data”. When I google it, I find that there is no clear definition in spite of its “wide” usage (in specific domains).
Can someone explain this concept to me?
 A: Good answers by Matt (+1) and others. Just to have a picture to drive the message (visually) home. In the following figure assuming that the squares represent sampling points the grey boxes follow an obvious regularly spaced design; the red box are just random samples that are irregularly spaced.

Both designs have their pros and cons. Do not dismiss the irregular design as "worse". For example, certain adaptive sampling designs can be extremely helpful for density estimation but highly irregular strictly speaking. That is because you mostly care for regions of high volatility. Numerical integration schemes are a standard example. On the one hand, the trapezoid rule (and in general all the Newton–Cotes formulas) is based an equally spaced sampling technique. On the other hand Monte Carlo integration methods might a strongly irregular sample that sometimes can deviate a lot from being uniform and equally spaced (eg. importance sampling).
A: This usually means that there is no clear underlying structure of the position of the points. I.e. it is not a rectangular grid or anything that can be represented compactly which has a clear structure.
Imagine that you have weather stations around a country and you are monitoring temperature. These weather stations are most likely no on any specifically defined grid. They are irregularly spaced and thus if one wants to do any spatial inference, one needs to create some spatial graph/mesh, most often made of triangles. Then one can do inference and interpolations based on the values at the known weather stations. 
This is highly dependent on which mesh/graph you select, so there are different techniques to generate them.
A: A lot of techniques assume that data is sampled at regularly-spaced intervals. You might count how much litter is near each mile marker on the highway, or sample points in a forest on a regularly spaced grid (100, 200, 300, ... meters north and 100, 200, 300 meters east of some landmark). This also occurs in time--my EEG machine records a data point every millisecond. We call the interval between adjacent samples the sampling period.
However, a lot of data is not or cannot be sampled with a fixed sampling period. Perhaps the terrain doesn't allow us to place weather stations exactly 50 miles apart. We often study peoples' heights and weights, but these are only opportunistically measured at doctors' appointments (which are often not exactly 1 year apart). These data are irregularly sampled.
The paper you linked describes methods for dealing with the latter kind of data, where the sampling period is not constant. One possible approach is to interpolate your data onto a grid and then use a techniques intended for gridded data. The paper argues that while this works in 1 dimension, it is less satisfactory in multiple dimensions and their lifting-based approach works better. 
A: It's a british way of saying that your data does not come evenly spaced. Say, you measure the temperature on the road, and obtain the observation every 1 mile apart. This would be regularly spaced data. As opposed to taking measurements at every gas station, which would not be equally spaced, of course.
