Please help me find a simple (geometric?) problem
For an example for some research I'm working on, I need to think of a problem - it can be anything, but a simple (possibly geometric) problem would be ideal - where the problem can be formulated as a number of inputs, say I_1, ..., I_n, and we are interested in several properties of the problem (outputs O_1, ..., O_m) that can be calculated from
( Read more... )
Comments 4
If I_1,I_2,...I_n are dots in R^2, O_1,O_2,...,O_m could be numbers of all convex quadrilateral, pentagon,...m+3 polygons, constructed from the input points.
Or minimal weight of connected subset of order m+1.
Reply
Reply
I'm assuming inputs would be the points S serving as the seeds / generators / centres, and the outputs would be the classifications for each other point in the space. I'm just confused how, for a point X not in S, the set of "inputs" determining X isn't all of S.
(Reading over my original post, maybe I wasn't clear enough... I'm looking for a problem where there are at least two outputs, say X1 and X2, and the set of inputs determining X1, say J1, and the set of inputs determining X2, say J2, have the property that J1 != J2, J1 not subset J2, and J2 not subset J1. They can intersect, but I'd like each to contain elements not in the other.)
If I can use the Voroni cell problem, that would be fantastic, but I'm not sure in advance how to do so.
Reply
Roughly speaking, each input point will only have an impact on the polygons 'near' it, and likewise, the output polygons will be determined only by the 'nearby' points. So, given enough input points, each output polygon will be determined by a different subset of the inputs.
It's also a well-studied problem so the algorithm should be easy to implement. Hope this helps.
Reply
Leave a comment