# Mapping discrete variables

Let's say I have a set of discrete, arbitrary variables sampled at continuous co-ordinates, e.g.

==================================
= x       = y       = Value      =
==================================
= 4.1     = 3.4     = A          =
= 4.6     = 7.9     = A          =
= 4.7     = 8.1     = A          =
= 2.1     = 5.0     = B          =
= 3.5     = 9.0     = B          =
= 7.0     = 1.1     = C          =
= 9.8     = 4.2     = C          =
==================================


I would like to generate a map showing the distribution of the values across a range of co-ordinates (e.g. 0<x<=10, 0<y<=10), where each value has an arbitrary colour assigned, and every point within those co-ordinates has a calculated interpolated value, where it is reasonable to do so.

E.g. we give a colour to each of A, B and C.

the point (5.0,5.0) is in the middle of the cluster of As so should be coloured as per A.

the point (7.0,4.0) is between the As and Cs so the colour should be calculated via some analysis of distance to each of those surrounding points.

Broadly I would expect the top-left quadrant to be a colour assigned to B, the bottom right quadrant to be a colour assigned to C, with a band of colour assigned to A between and the point at which the boundaries between the 3 colours occur calculated via some kind of nearest-neighbour algorithm.

Are there any existing algorithms to map the kind of information I wish to display? It should take into account any inliers (if that's the right term).

• What kind of thing or observation do these values represent?
– whuber
Oct 26, 2011 at 21:03
• survey responses from people at given geographical locations Oct 27, 2011 at 10:06
• Ah! What sense does it make to interpolate categorical survey responses over a map, then? Your answer to this will suggest appropriate interpolation methods.
– whuber
Oct 27, 2011 at 16:46

First thing that popped to my mind were Voronoi diagrams, though those are not inlier-safe.

If you do have a lot of noise, explore kNN algorithms.

• In the GIS world--which is the natural place to look for tools to solve this problem--Voronoi diagrams are also known as Thiessen polygons and Euclidean allocations. Some people use ad hoc methods to remove the inliers, such as performing morphological operations or local filtering (e.g., a majority filter) to clean the resulting images.
– whuber
Oct 26, 2011 at 18:44
• Inliers are naturally down-weighted by a kNN-like algorithm. Depending on how the inliers come about, cleaning may or may not work. In particular, for extended boundaries between classes, there will be lines where majority will not work because it is simply 50/50. In fact there are classifiers that are based on that property. Oct 26, 2011 at 18:58
• I didn't say these were good methods; I was just reporting what people do :-). However, if there's an "extended line" bounding a region, it doesn't sound like it would qualify to be an inlier and probably should be kept as is. Or do you perhaps have a probability model for these data that underlies your thinking?
– whuber
Oct 26, 2011 at 21:00
• Not really. And multi-dimensional PDF estimation sounds like a challenge. Oct 26, 2011 at 21:32
• thank you, knn looks exactly the algorithm I am looking for, and lots of lovely pre-existing code :) Oct 27, 2011 at 11:06