If there's a polyline (a GPS track, actually) with a lot of points (could be several thousand), that looks like this
1) How can I find such a triangle with the biggest possible perimeter, that its vertices belong to the polyline? In addition, it have to satisfy some constraint - for example, this one below satisfies 28% leg rule (the shortest leg must not be less than 28% of the total leg distance).
2) A related problem; although, I suppose, it should be easier. How can I approximate this polyline with a much simpler broken line with N breakpoints? Like in the example above (4 breakpoints).
Thanks.
You could iterate ovedr all point triples and check each. To make things slightly more effective, you could skip looking for third points if a pair you're investigating can only lead to triangles smaller than the best known so far, avvording to that $28\%$ rule.
Depends on how you measure error. Conceptually you could again try all possible break points and remember the best. For more efficient approasches, you might start by reading How to intelligently degrade or smooth GIS data (simplifying polygons), the Wikipedia article on the Ramer-Douglas-Peucker algorithm and the alternatives and survey papers mentioned therein. Most such approaches are controlled by a bound on the error, not by the number of segments, but you might be able to adapt them.