Hi. The algorithms in GEOS are almost all ported from the JTS Topology Suite, fyi.
The reason for not having explicit documentation for algorithm complexity is time/effort, and difficulty of proving the complexity. In general the algorithms should be roughly O(n log n) (as opposed to the O(n^2) that would result from a naive implementation, which is too slow for production use). The complexity may also be data-dependent, since despite best efforts there may be one or two O(n^2) steps in the code for certain geometry cases. On Thu, Sep 3, 2020 at 6:46 AM Zachary Déziel <[email protected]> wrote: > Hi all, > > > > Sorry for disturbing and I hope I am passing through the right channel for > my question. If not, please feel free to redirect me! > > > > I have been searching in the documentation and elsewhere for information > regarding the time complexity of the algorithms of GEOS. More precisely > around the classic operations on point, line and polygon data structures > (buffer, intersect, etc). The only mention of complexity I found was > regarding a trade-off between simplicity for the intersection method. Is > there some hidden documentation somewhere that covers the time and/or > memory complexity of the algorithms? If no such documentation exists, are > there reasons for it not existing? Is it simply a matter of not being a > priority in the development cycle? > > > > Sorry for the compact and numerous questions, if you have any interest in > the subject please reach out. > > > > Sincerely, > > > > Zachary Deziel > > > _______________________________________________ > geos-devel mailing list > [email protected] > https://lists.osgeo.org/mailman/listinfo/geos-devel
_______________________________________________ geos-devel mailing list [email protected] https://lists.osgeo.org/mailman/listinfo/geos-devel
