get a point in polygon (maximize the distance from borders) I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders (then one point that is the farthest one from the borders can be chosen..).
The polygons may contain holes, but there are no edges intersections. The number of vertices can be also quite large (up to 500 vertices or so).
If the condition that the polygons may have holes is restrictive, you may neglect it. However, if the holes are present, they are "known" (e.g. the order of points in the outer boundary is clockwise, and the order of points in holes is then counterclockwise).
I saw Get a point inside a polygon and Finding a point farthest away from k points in a polygon, but these links are still not really suitable for the problem described above.
I'm glad to receive any suggestions about possibly simple solution approaches for my question. The maximization of the distance from the borders is the highest goal, but actually it suffices to ensure that the picked points are inside the polygon and not closer to the borders than some predetermined distance.
 A: Perhaps it will help to investigate the medial axis of a polygon.
It was discussed in this earlier MO question, Retraction of a Riemannian manifold with boundary to its cut locus.
The junctions of the medial axis are points that are far from the boundary,
centers of disks touching the boundary at three or more points—local maxima,
to quote from Wlodek's comment.
The medial axis can be
computed for polygons with holes as well:

 


 
 
 
 
 (Image from this Matlab link)
It would be "straightforward" (with the right software) to compute for several thousand vertices. All computations also compute the disks radii, so with the medial axis in hand,
one can select the disk of maximal radius.

You may also find papers that focus directly on the largest incircle of a polygon, e.g.,
"An Efficient Algorithm to Calculate 
the Center of the Biggest Inscribed 
Circle in an Irregular Polygon" (arXiv link).
A: You seem willing to accept non-optimal solutions as long as they lead to optimal solutions.  For convex polygons, I suggest using a midpoint method: pick pairs of vertices (ideally they are presented in clockwise order, so if $k = \lfloor n/2 \rfloor$ you could try pairs 
$(v_i, v_{i+k})$) and use their midpoints.  The locus of many of these will have a center of mass that should be near your optimal point.  You could also use an average of all vertices as a candidate.
If the polygon is not convex, you could run this with a selection of pairs and find
a point that would be far from the edges but be OUTSIDE of the polygon.  My recommendation
would be to settle on finding a subpolygon (say a triangle sharing two edges with the original polygon) that is convex and contained within the entire polygon, and generate points for that.
It wouldn't be far from all edges, but it would be far from all but two of the edges.
If the polygon has holes, all bets are off: if you use any proper subset of the vertices, you may end up with the desired points in a triangular hole.  Again you can try the subpolygon idea, but unless you have an oracle that tells you when you are in the interior, you will likely need to sample a large number (if not all) of the vertices.
Gerhard "Specializes In Dirty And Quick" Paseman, 2014.03.26
