[SoC] project idea - implementing shortest path graph and stepping stone graph

Sameera Kannangara dlskannangara at gmail.com
Thu Feb 27 17:15:59 PST 2020


Hi OSGeo GSoC mentors,

I'm Sameera Kannangara, a PhD student from the university of Melbourne. My
PhD is on spatial data analysis of location based social network data. As
part of my research work I have implemented Delaunay triangulation [1],
Gabriel graph [2] and shortest-path graph [3]. Also I have introduced a new
graph named stepping stone graph [4] and presented it at SIGSPATIAL 2018
conference. We got nominated for the best paper award and were invited to
extend and publish the paper in journal of ACM Transactions on Spatial
Algorithms and Systems [5]. Stepping stone graph has a wide variety of use
cases such as inferring movement corridors, evaluating nearest neighbour
queries, Inferring travel networks, most popular path finding, tour
recommendation, trajectory clustering and group movement detection. For
some of the use cases we need trajectory information which can be found
from social media on top of spatial data.I have soft copies of both papers
if anyone is interested.

As a part of my research project implementation, I have been a user of
GeoTools [6] project for over 3 years now. I have heavily used GeoTools UI
and basic structures such as coordinates and spatial indexes in my
calculations. I have crude implementations of S-hull algorithm for creating
Delaunay triangulation, shortest path graph and stepping stone graph, which
I would like to contribute to the GeoTools project. Shortest path graph is
also useful when determining boundaries of imprecise regions given as a
coordinate set. I would like to know the possibility of doing these
contributions as a GSoC 2020 project. Thank you for your consideration and
hope to hear from you soon.

Best wishes,
Sameera

[1] https://en.wikipedia.org/wiki/Delaunay_triangulation
[2] https://en.wikipedia.org/wiki/Gabriel_graph
[3] https://en.wikipedia.org/wiki/Shortest-path_graph
[4] https://dl.acm.org/doi/10.1145/3274895.3274913
[5] https://dl.acm.org/doi/abs/10.1145/3324883
[6] https://geotools.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20200228/4113816f/attachment.html>


More information about the SoC mailing list