[Octave-bug-tracker] [bug #55751] scatter3 performance regression bug in Octave 5.0.91

[Eddy]

Follow-up Comment #17, bug #55751 (project octave):

New idea comes, try the attached patch, it is the method (2) below. The patch
is primary for conceptual verification, no thoughtful test or careful cover of
every edge case.

With this patch, the time cost for the initial reported sample is reduced to
roughly 0.3 second, and the said ever-running example will end in 0.32
second.

Read a bit about graphics.cc and bug #47677.

The current algorithm there, for non-coplanar random data of n points, the
time cost is roughly O(n^3): one n for a single coplanar test, one n for
search the largest coplanar point set, last n for repeated search of each
plane.

I can see at least two possible optimizations.

1. Use binary search instead of the full linear search. 
This reduce the time cost to O(n^2 log(n)).

2. Incremental search for coplanar point set. 
This is based on the observation that in the 'eig' method: eig(a'*a), the 3x3
matrix a'*a can be calculated by rank one updates corresponding to each point.
Thus we can check if the newly added point is inside the plane or not in O(1)
(one eig of 3x3 matrix). Time cost is thus reduced to O(n).

To further speed (if necessary), we may need to know the more frequent use
case of patch():
a. large list of many non coplanar input. or
b. coplanar input.

If it is (b), probably adding an initial overall coplanar test can help, at
the cost of slow down case (a). Current implementation favors (a).

(file #46431)
    _______________________________________________________

Additional Item Attachment:

File name: bug55751_inc_coplanar.patch    Size:4 KB
    <https://savannah.gnu.org/file/bug55751_inc_coplanar.patch?file_id=46431>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?55751>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/