Search Results

Documents authored by Wisnosky, David


Document
Media Exposition
Visualizing WSPDs and Their Applications (Media Exposition)

Authors: Anirban Ghosh, FNU Shariful, and David Wisnosky

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Introduced by Callahan and Kosaraju back in 1995, the concept of well-separated pair decomposition (WSPD) has occupied a special significance in computational geometry when it comes to solving distance problems in d-space. We present an in-browser tool that can be used to visualize WSPDs and several of their applications in 2-space. Apart from research, it can also be used by instructors for introducing WSPDs in a classroom setting. The tool will be permanently maintained by the third author at https://wisno33.github.io/VisualizingWSPDsAndTheirApplications/.

Cite as

Anirban Ghosh, FNU Shariful, and David Wisnosky. Visualizing WSPDs and Their Applications (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 68:1-68:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.SoCG.2022.68,
  author =	{Ghosh, Anirban and Shariful, FNU and Wisnosky, David},
  title =	{{Visualizing WSPDs and Their Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{68:1--68:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.68},
  URN =		{urn:nbn:de:0030-drops-160760},
  doi =		{10.4230/LIPIcs.SoCG.2022.68},
  annote =	{Keywords: well-separated pair decomposition, nearest neighbor, geometric spanners, minimum spanning tree}
}
Document
Media Exposition
An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)

Authors: Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
The construction of bounded-degree plane geometric spanners has been a focus of interest in the field of geometric spanners for a long time. To date, several algorithms have been designed with various trade-offs in degree and stretch factor. Using JSXGraph, a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms so that they can be used for further research and teaching computational geometry. We believe that our interactive tool can be used by researchers from related fields to understand and apply the algorithms in their research. Our tool can be run in any modern browser. The tool will be permanently maintained by the second author at https://ghoshanirban.github.io/bounded-degree-plane-spanners/index.html

Cite as

Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky. An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 61:1-61:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.SoCG.2021.61,
  author =	{Anderson, Fred and Ghosh, Anirban and Graham, Matthew and Mougeot, Lucas and Wisnosky, David},
  title =	{{An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{61:1--61:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.61},
  URN =		{urn:nbn:de:0030-drops-138607},
  doi =		{10.4230/LIPIcs.SoCG.2021.61},
  annote =	{Keywords: graph approximation, Delaunay triangulations, geometric spanners, plane spanners, bounded-degree spanners}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail