<div dir="ltr">Hi.  The algorithms in GEOS are almost all ported from the JTS Topology Suite, fyi.  <div><br></div><div>The reason for not having explicit documentation for algorithm complexity is time/effort, and difficulty of proving the complexity. </div><div><br></div><div>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.  </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Sep 3, 2020 at 6:46 AM Zachary Déziel <<a href="mailto:Zachary.Deziel@usherbrooke.ca">Zachary.Deziel@usherbrooke.ca</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">





<div lang="EN-CA">
<div class="gmail-m_595902026101542839WordSection1">
<p class="MsoNormal">Hi all, <u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Sorry for disturbing and I hope I am passing through the right channel for my question. If not, please feel free to redirect me!<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">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?
<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Sorry for the compact and numerous questions, if you have any interest in the subject please reach out.
<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Sincerely,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Zachary Deziel<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>

_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a></blockquote></div>