11 papers
On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs
Benedikt Kolbe, Jack Spalding-Jamieson
In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface…
The Presort Hierarchy for Geometric Problems
Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson +1
Many fundamental problems in computational geometry admit no algorithm running in time for planar input points, via classical reductions from sorting. Prominent e…
Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
Jayson Lynch, Jack Spalding-Jamieson
The (unweighted) point-separation problem asks, given a pair of points and in the plane, and a set of candidate geometric objects, for the minimum-size subset of objects wh…
Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
Jack Spalding-Jamieson
We establish that a practical polynomial-time algorithm obtains near-optimal -balanced vertex separators for a number of graph classes, including genus- graphs, -m…
Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
Jack Spalding-Jamieson, Anurag Murty Naredla
Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimu…
Slant/Gokigen Naname is NP-complete, and Some Variations are in P
Jayson Lynch, Jack Spalding-Jamieson
In this paper we show that a generalized version of the Nikoli puzzle Slant is NP-complete. We also give polynomial time algorithms for versions of the puzzle where some constraint…
Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
Jack Spalding-Jamieson, Eliot Wong Robson, Da Wei Zheng
For very large values of , we consider methods for fast -means clustering of massive datasets with points in high-dimensions (). All current practica…
The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving
Eliot W. Robson, Jack Spalding-Jamieson, Da Wei Zheng
We show the following problems are in : 1. The contiguous art gallery problem -- a variation of the art gallery problem where each guard can protect a contiguous interv…
Carving Polytopes with Saws in 3D
Eliot W. Robson, Jack Spalding-Jamieson, Da Wei Zheng
We investigate the problem of carving an -face triangulated three-dimensional polytope using a tool to make cuts modelled by either a half-plane or sweeps from an infinite ray.…
Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Loïc Crombez, Guilherme D. da Fonseca, Florian Fontan +8
CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the to…
Coordinated Motion Planning Through Randomized k-Opt
Paul Liu, Jack Spalding-Jamieson, Brandon Zhang +1
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 gi…