Author: asargadmin

Posted on

Relocation with Uniform External Control in Limited Directions

Title: Relocation with Uniform External Control in Limited Directions (Short Abstract)
Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.
Conference: The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’19), 2019.

Abstract: We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-Complete with $1 \times 1$ particles even when only allowed to move in 2 or 3 directions.

Posted on

Discrete Planar Map Matching

Title: Discrete Planar Map Matching

Authors: Bin Fu, Robert Schweller, Tim Wylie

Conference: The 31st Canadian Conference on Computational Geometry (CCCG’19)

Abstract:

Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the Frechet distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often only approximate location data. This process can be approximated by sampling the curves and using the discrete Frechet distance. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous Frechet distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. We give an efficient algorithm to solve one and prove the other is NP-complete and the minimization version is APX-hard while also giving a parameterized algorithm to solve the problem.

Posted on

Paper accepted at CCCG 2019

We have just had a paper accepted to the 31st Canadian Conference on Computational Geometry. The paper is titled “Discrete Planar Map Matching” authored by Bin Fu, Robert Schweller, and Tim Wylie. For more information visit the publication page.