Problem 820. Eliminate unnecessary polygon vertices

Solution 110965

Submitted on 12 Jul 2012 by Sven

Correct

45Size

Leading solution size is 36.

This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Solve This Problem View on Solution Map View Details

7 Comments

Show 4 older comments

Richard Brown on 12 Jul 2012

Nicely done! Do you think we've converged on the optimum yet?

Sven on 12 Jul 2012

Cheers, obviously I shamelessly adopted your favourite function. I honestly thought we'd converged to an optimum (although a slightly distorted use of that word) back at around 64, then 55, then 48... so I only tentatively think we've reached the end. I'd certainly be relieved to call it a draw :)

Sven on 12 Jul 2012

I thought that maybe we could get rid of the extra arguments to sum(,2) and any(,2) by converting to a row matrix, but doing so would add arguments circshift(), so that way may not have any improvements left. I do know that *every single line* of our function generates an M-Lint warning :) Oh, except the function name now.

Richard Brown on 12 Jul 2012

Yeah, I tried all sorts of ways to do that too! I was trying to figure out a better way to normalise the matrix. I discovered normr, posted my solution, and then realised that it was actually a toolbox function. I'd be happy to have that entry removed :| If you replace the normalisation line with normr(diff(P)) you can get the 36

Sven on 12 Jul 2012

Hah, "Undefined function or variable 'normr'." A while back I had a version with normalizeVector3d(), part of the geom3d() package I use all the time... I'd be interested to see under the hood of normr... I hope it's vectorized via bsxfun()

Richard Brown on 13 Jul 2012

no it doesn't! it does something like: n = sqrt(sum(x.^2,2)); x = x ./ n(:, ones(1, size(x,2)));

Sven on 13 Jul 2012

Well then, I bet that the following would run faster and work on any dimensioned data (such as a [10,2,50] sized matrix representing 50 sets of 10 XY vectors): normr = @(v)bsxfun(@rdivide, v, sqrt(sum(v.^2, 2)));