[geos-devel] Complexity of algorithms

Martin Davis mtnclimb at gmail.com
Thu Sep 3 09:37:59 PDT 2020


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 <Zachary.Deziel at usherbrooke.ca>
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
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20200903/1972b40d/attachment.html>


More information about the geos-devel mailing list