Publications

[Cha17]

Hubert Chathi. whalebuilder: building packages with Docker. DebConf conference presentation, August 2017. [ http ]

[Cha12]

Hubert Chathi. Integrating Moodle with an external tool. iMoot conference presentation, May 2012. [ http ]

[Cha04]

Hubert Chan. A parameterized algorithm for upward planarity testing (extended abstract). In Susanne Albers and Tomasz Radzik, editors, Proceedings of 12th annual European Symposium on Algorithms 2004, volume 3221 of Lecture Notes in Computer Science, pages 157-168, 2004. [ http | .pdf ]

Upward planarity testing, or checking whether a directed graph has a drawing in which no edges cross and all edges point upward, is NP-complete. All of the algorithms for upward planarity testing developed previously focused on special classes of graphs. In this paper we develop a parameterized algorithm for upward planarity testing that can be applied to all graphs and runs in O(f(k)n³ + g(k,l)n) time, where n is the number of vertices, k is the number of triconnected components, and l is the number of cutvertices. The functions f(k) and g(k,l) are defined as f(k)=k!8^k and g(k,l)=2^{3· 2^l}k^{3·2^l} k!8^k. Thus if the number of triconnected components and the number of cutvertices are small, the problem can be solved relatively quickly, even for a large number of vertices. This is the first parameterized algorithm for upward planarity testing.

[Cha03]

Hubert Chan. A parameterized algorithm for upward planarity testing of biconnected graphs. Master's thesis, University of Waterloo, May 2003. [ http ]

We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two endpoints.

Directed graphs are often used to model hierarchical structures; in order to visualize the hierarchy represented by such a graph, it is desirable that a drawing of the graph reflects this hierarchy. This can be achieved by drawing all the edges in the graph such that they all point in an upwards direction. A graph that has a drawing in which all edges point in an upwards direction and in which no edges cross is known as an upward planar graph. Unfortunately, testing if a graph is upward planar is NP-complete.

Parameterized complexity is a technique used to find efficient algorithms for hard problems, and in particular, NP-complete problems. The main idea is that the complexity of an algorithm can be constrained, for the most part, to a parameter that describes some aspect of the problem. If the parameter is fixed, the algorithm will run in polynomial time.

In this thesis, we investigate contracting an edge in an upward planar graph that has a specified embedding, and show that we can determine whether or not the resulting embedding is upward planar given the orientation of the clockwise and counterclockwise neighbours of the given edge. Using this result, we then show that under certain conditions, we can join two upward planar graphs at a vertex and obtain a new upward planar graph. These two results expand on work done by Hutton and Lubiw [?].

Finally, we show that a biconnected graph has at most k!8^k-1 planar embeddings, where k is the number of triconnected components. By using an algorithm by Bertolazzi et al. [?] that tests whether a given embedding is upward planar, we obtain a parameterized algorithm, where the parameter is the number of triconnected components, for testing the upward planarity of a biconnected graph. This algorithm runs in O(k!8^kn³) time.

[BCK01]

David J. Ballantyne, Hubert Y. Chan, and Michael A. Kouritzin. A branching particle-based nonlinear filter for multi-target tracking. In Proceedings of 4th Annual Conference on Information Fusion, pages We2-3-WeA2-10, 2001.

A branching particle-based filter is used to detect and track multiple simulated maneuvering ships in a region of water. The ship trajectories exhibit nonlinear dynamics and interact in a nonlinear manner so that the ships to not collide. There is no a priori knowledge of the number of ships in the region.

Observations model a sensor tracking the ships from above the region as in a low observable problem. The branching filter simplates particles, each of which is a sample from the domain of possible combinations of ship number and the state of those ships, and each of which is evolved independently using the stochastic law of the signal between observations. The branching filter employs these particles to provide the approximated conditional distribution of the signal in the combined domain, given all observations. Quantitative results recording the cabacity of the branching filter to determine the number of ships in the region and the location of each ship are presented.

Keywords: tracking, particle-based filtering, multiple target, branching filter, nonlinear filtering

[CK01]

Hubert Y. Chan and Michael A. Kouritzin. Particle filters for combined state and parameter estimation. In Ivan Kadar, editor, Signal Processing, Sensor Fusion, and Target Recognition X, volume 4380 of Proceedings of SPIE, pages 244-252, 2001. [ http | .pdf ]

Filtering is a method of estimating the conditional probability distribution of a signal based upon a noisy, partial, corrupted sequence of observations of the signal. Particle filters are a method of filtering in which the conditional distribution of the signal state is approximated by the empirical measure of a large collection of particles, each evolving in the same probabilistic manner as the signal itself.

In filtering, it is often assumed that we have a fixed model for the signal process. In this paper, we allow unknown parameters to appear in the signal model, and present an algorithm to estimate simultaneously both the parameters and the conditional distribution for the signal state using particle filters. This method is applicable to general nonlinear discrete-time stochastic systems and can be used with various types of particle filters. It is believed to produce asymptotically optimal estimates of the state and the true parameter values, provided reasonable initial parameter estimates are given and further estimates are constrained to be in the vicinity of the true parameters.

We demonstrate this method in the context of search and rescue problem using two different particle filters and compare the effectiveness of the two filters to each other.

Keywords: nonlinear filtering, parameter estimation, target tracking, particle methods, system identification

[BCK00]

David J. Ballantyne, Hubert Y. Chan, and Michael A. Kouritzin. A novel branching particle method for tracking. In Oliver E. Drummond, editor, Signal and Data Processing of Small Targets, volume 4048 of Proceedings of SPIE, pages 277-287, 2000. [ http ]

Particle approximations are used to track a maneuvering signal given only a noisy, corrupted sequence of observations, as are encountered in target tracking and surveillance. The signal exhibits nonlinearities that preclude the optimal use of a Kalman filter. It obeys a stochastic differential equation (SDE) in a seven-dimensional state space, one dimension of which is a discrete maneuver type. The maneuver type switches as a Markov chain and each maneuver identifies a unique SDE for the propagation of the remaining six state parameters. Observations are constructed at discrete time intervals by projecting a polygon corresponding to the target state onto two dimensions and incorporating the noise.

A new branching particle filter is introduced and compared with two existing particle filters. The filters simulate a large number of independent particles, each of which moves with the stochastic law of the target. Particles are weighted, redistributed, or branched, depending on the method of filtering, based on their accordance with the current observation from the sequence. Each filter provides an approximated probability distribution of the target state given all back observations.

All three particle filters converge to the exact conditional distribution as the number of particles goes to infinity, but differ in how well they perform with a finite number of particles. Using the exactly known ground truth, the root-mean-squared (RMS) errors in target position of the estimated distributions from the three filters are compared. The relative tracking power of the filters is quantified for this target at varying sizes, particle counts, and levels of observation noise.

Keywords: nonlinear filtering, branching interacting particle method, target tracking

[CLS97]

Hubert Chan, Andy Liu, and Andrei Storozhev. Induction in geometry. Mathematics Competitions, 10:61-68, 1997.

[CLvV92]

Hubert Chan, Steven Laffin, and Daniel van Vliet. Knight tours. Mathematics and Informatics Quarterly, 2:135-150, 1992.

This file was generated by bibtex2html 1.95.