# Determining closest representation of polygon as collection of points+radii

Have a bit of a tough question, which I realize there may not be an easy solution to. Figured what better place to ask.

I'm attempting to transform a polygon into a series of arbitrary points with arbitrary radii (circles!) that best represent the area covered by the polygon.

Minor over- and underflow is acceptable, as is circle-overlap, in hopes of achieving an efficient solution (i.e. fewest possible points, no gaps).

Ideally, a given poly would be represented by a few large circles, and several smaller circle on the perimeters.

Essentially, the problem is that I have a dynamic number of polys that get hit on geo-spatial queries given a specific gps coordinate, however, we are required to move to a system wherein I will not be able to utilize a point-within-poly query, but will have to rely on point-within-distance queries.

Hopefully someone has at least attempted something similar, and, if not, hopefully someone is willing to throw some ideas around!

Open to most languages, but this needs to be done programmatically!

My point is that I feed indexes to the system and I get alerted when they are hit. I don't perform any queries on this system myself (black box), so I wouldn't have control enough to negate a query. That's the reason I need to transform the poly to a representation of points.

-
A slight generalization (that nevertheless may greatly streamline your queries) is to represent a polygon in terms of the set difference between two unions of circles: this lets you, for instance, start with a circle that wholly encloses the polygon and then remove circular regions from it (and add more back in) in order to approximate the polygon. This is a 2D version of constructive solid geometry whose only primitives are disks. – whuber Aug 21 '13 at 21:05
Well, as far as queries go, it would be a 3rd party system, which I have little control over. I'm only forced use point-with-radius as the index. As far as that system is concerned we aren't even dealing with polygons anymore. Point being, I'm not sure if this transformation would benefit me, as I am not able to utilize circle subtraction. Circles are only meant to represent distance in my problem. If that makes sense. – derrrrrick Aug 21 '13 at 21:39
Circle subtraction corresponds to negating a query: surely you can do that! – whuber Aug 21 '13 at 21:58
Haha, sorry, my point was that I feed indexes to the system and I get alerted when they are hit. I don't perform any queries on this system myself, so I wouldn't have control enough to negate a query. That's the reason I need to transform the poly to a representation of points in the first place :) – derrrrrick Aug 21 '13 at 22:01
It seems important to include that last information in the question itself so that readers understand what you need. Just to be clear: are you saying that your "indexes" consist of disks, that all you can do is get an alert when a probe point hits a disk (and presumably that alert identifies the disk(s) it hit), and you wish to construct a system to be alerted whenever a probe falls within an arbitrary polygon? Also, is it possible to pre-process probe point coordinates (such as projecting or unprojecting them) before they are sent to this system? – whuber Aug 22 '13 at 11:59