Search Results

Documents authored by Spalding-Jamieson, Jack

Document
DOI: 10.4230/LIPIcs.GD.2024.40
Morphing Planar Graph Drawings via Orthogonal Box Drawings

Authors: Therese Biedl, Anna Lubiw, and Jack Spalding-Jamieson

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
We give an algorithm to morph planar graph drawings that achieves small grid size at the expense of allowing a constant number of bends on each edge. The input is an n-vertex planar graph and two planar straight-line drawings of the graph on an O(n) × O(n) grid. The planarity-preserving morph is composed of O(n) linear morphs between successive pairs of drawings, each on an O(n) × O(n) grid with a constant number of bends per edge. The algorithm to compute the morph runs in O(n²) time on a word RAM model with standard arithmetic operations - in particular no square roots or cube roots are required. The first step of the algorithm is to morph each input drawing to a planar orthogonal box drawing where vertices are represented by boxes and each edge is drawn as a horizontal or vertical segment. The second step is to morph between planar orthogonal box drawings. This is done by extending known techniques for morphing planar orthogonal drawings with point vertices.
Cite as

Therese Biedl, Anna Lubiw, and Jack Spalding-Jamieson. Morphing Planar Graph Drawings via Orthogonal Box Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.GD.2024.40,
  author =	{Biedl, Therese and Lubiw, Anna and Spalding-Jamieson, Jack},
  title =	{{Morphing Planar Graph Drawings via Orthogonal Box Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.40},
  URN =		{urn:nbn:de:0030-drops-213242},
  doi =		{10.4230/LIPIcs.GD.2024.40},
  annote =	{Keywords: morphing, graph morphing, linear morph, planar graph drawing, orthogonal box drawing, orthogonal drawing, algorithm}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2022.72
Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

Authors: Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

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

Abstract
This paper examines the approach taken by team gitastrophe in the CG:SHOP 2022 challenge. The challenge was to partition the edges of a geometric graph, with vertices represented by points in the plane and edges as straight lines, into the minimum number of planar subgraphs. We used a simple variation of a conflict optimizer strategy used by team Shadoks in the previous year’s CG:SHOP to rank second in the challenge.
Cite as

Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 72:1-72:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{spaldingjamieson_et_al:LIPIcs.SoCG.2022.72,
  author =	{Spalding-Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title =	{{Conflict-Based Local Search for Minimum Partition into Plane Subgraphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{72:1--72:6},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.72},
  URN =		{urn:nbn:de:0030-drops-160807},
  doi =		{10.4230/LIPIcs.SoCG.2022.72},
  annote =	{Keywords: local search, planar graph, graph colouring, geometric graph, conflict optimizer}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2021.64
Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)

Authors: Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

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

Abstract
This paper examines the approach taken by team gitastrophe in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two given configurations that minimized either total distance travelled or makespan (total time). Our winning approach has two main components: an initialization phase that finds a good initial solution, and a k-opt local search phase which optimizes this solution. This led to a first place finish in the distance category and a third place finish in the makespan category.
Cite as

Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Coordinated Motion Planning Through Randomized k-Opt (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 64:1-64:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.SoCG.2021.64,
  author =	{Liu, Paul and Spalding-Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title =	{{Coordinated Motion Planning Through Randomized k-Opt}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{64:1--64:8},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.64},
  URN =		{urn:nbn:de:0030-drops-138635},
  doi =		{10.4230/LIPIcs.SoCG.2021.64},
  annote =	{Keywords: motion planning, randomized local search, path finding}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2020.83
Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)

Authors: Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The Minimum Convex Partition problem (MCP) is a problem in which a point-set is used as the vertices for a planar subdivision, whose number of edges is to be minimized. In this planar subdivision, the outer face is the convex hull of the point-set, and the interior faces are convex. In this paper, we discuss and implement the approach to this problem using randomized local search, and different initialization techniques based on maximizing collinearity. We also solve small instances optimally using a SAT formulation. We explored this as part of the 2020 Computational Geometry Challenge, where we placed first as Team UBC.
Cite as

Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang. Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 83:1-83:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.SoCG.2020.83,
  author =	{Zheng, Da Wei and Spalding-Jamieson, Jack and Zhang, Brandon},
  title =	{{Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{83:1--83:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.83},
  URN =		{urn:nbn:de:0030-drops-122412},
  doi =		{10.4230/LIPIcs.SoCG.2020.83},
  annote =	{Keywords: convex partition, randomized local search, planar point sets}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact