#### Lab Events

July 20, 2016 (E2-553)
Research discussion
Coordinated by : Yeganeh Bahoo Torudi
Discussion topic : Polygon Simplification by Minimizing Convex Corners (SOFSEM 2015).

Abstract. Let P be a polygon with r>0 reflex vertices and possibly with holes. A subsuming polygon of P is a polygon P' such that P ⊆ P', each connected component R' of P' subsumes a distinct component R of P, i.e., R⊆ R', and the reflex corners of R coincide with the reflex corners of R'. A subsuming chain of P' is a minimal path on the boundary of P' whose two end edges coincide with two edges of P. Aichholzer et al. proved that every polygon P has a subsuming polygon with O(r) vertices. Let \A(P) (resp., \Av(P)) be the arrangement of lines determined by the edges (resp., pairs of vertices) of P. Aichholzer et al. observed that a challenge of computing an optimal subsuming polygon P'_{min}, i.e., a subsuming polygon with minimum number of convex vertices, is that it may not always lie on \A(P). We prove that in some settings, one can find an optimal subsuming polygon for a given simple polygon in polynomial time, i.e., when \A(P'_{min}) = \A(P) and the subsuming chains are of constant length. In contrast, we prove the problem to be NP-hard for polygons with holes, even if there exists some P'_{min} with \A(P'_{min}) = \A(P) and subsuming chains are of length three. Both results extend to the scenario when \Av(P'_{min}) = \Av(P).
September 29, 2015 (E2-553)
Research discussion
Coordinated by : Yeganeh Bahoo Torudi
Discussion topic : Papers from CCCG 2015.

January 21, 2015 (E2-553)
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : On the Biplanar Crossing Number.

March 18, 2015 (E2-553)
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : On the paper Straight-Path Queries in Trajectory Data

April 1, 2015 (E2-553)
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Depth Measures.

April 15, 2015 (E2-553)
Research discussion
Coordinated by : Yeganeh Bahoo Torudi
Discussion topic : Shortest Paths in Polygons.

May 6, 2015 (E2-553)
Research discussion
Coordinated by : Sahar Mehrpour
Discussion topic : Shortest Paths and Visibility Queries.

May 20, 2015 (E2-553)
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : To be announced.

December 05, 2014 (E2-553)
Research discussion
Coordinated by : Sahar Mehrpour
Discussion topic : Pseudo-triangle Visibility Graphs.

November 21, 2014 (E2-553)
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Local Routing in Convex Subdivisions (SOFSEM 2015).

Abstract. In various wireless networking settings, node locations determine a network's topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ(log n) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).
November 07, 2014 (E2-553)
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Finding peak and shoulder in a data plot.

October 24, 2014 (E2-553)
Research discussion
Coordinated by : Yeganeh Bahoo Torudi
Discussion topic : On the Pursuit-Evasion Problems.

Abstract. In the problem of pursuit-evasion (PE), a polygon and some robots, which are called pursuers, are given. Most of pursuit-evasion problems ask for planning the motion of the pursuer in a polygon to eventually see all evaders. Applications of pursuit-evasion problem have been used in air traffic control, military strategy and trajectory tracking. In particular, I proposed geometric algorithms for three kinds of pursuers:

1. We introduce a new version of the pursuer which is called 2-modem. A 2-modem searcher is a wireless device whose radio signal can penetrate two walls. We will present a new cell decomposition of a given polygon P for the 2-modem searcher such that the combinatorial representation of the invisible regions of the searcher remains unchanged. Indeed, by this cell decomposition, we can find the strategy of the movement for the searcher so that it can detect all the evaders inside the polygon. At the end, we characterized the exact lines that crossing them causes that two invisible regions merge together. As a result, if a path is given (which does not intersect the boundary of the polygon), we can report if two invisible regions merge together.

2. We introduce a new version of the pursuer which the pursuer is a pi-searcher. A pi-searcher is a point robot equipped with pi-radian field of view (FOV) sensor. In fact, the searcher is considered a point robot. Furthermore, let s and t be two points inside P as the start and target points for the pi-searcher. Suppose that a query path from s to t is given for moving the searcher from s to t. The goal is to find a strategy for how to change the orientation of FOV so that no evader moves from an invisible region to another one without being detected by the searcher.

3. We consider a searcher which can see all of around itself at the same time and is looking for unpredictable evaders inside the polygon. First we assume that a query path is given, as a path for the robot's movement. We want to answer while the searcher moves on this path, invisible regions merge together or not. Secondly, instead of a path two points as the start and target points are given. We want to determine if there is a path between these two points for the searcher so that while it moves on this path, invisible regions do not merge together.
October 03, 2014 (E2-553)
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras (IWOCA 2014).

Abstract. A sliding camera travelling along a line segment s in a polygon P can see a point p in P if and only if p lies on a line segment contained in P that intersects s at a right angle. The objective of the minimum sliding cameras (MSC) problem is to guard P with the fewest sliding cameras possible, each of which is a horizontal or vertical line segment. In this paper, we give an O(n^3)-time 3-approximation algorithm for the MSC problem on any simple orthogonal polygon with n vertices. Our algorithm involves establishing a connection between the MSC problem and the problem of guarding simple grids with periscope guards.
September 19, 2014 (E2-553)
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Drawings with Small Height, and Trade-offs in Polyline Drawings (GD 2014).
August 27, 2014 (E2-553)
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Selected Papers from CCCG 2014.
March 26, 2014 (E2-553)
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Drawing HV-Restricted Planar Graphs.

Abstract. A strict orthogonal drawing of a graph G = (V;E) in R^2 is a drawing of G such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal or vertical line segment. A graph G is HV-restricted if each of its edges is assigned a horizontal or vertical orientation. A strict orthogonal drawing of an HV-restricted graph G is good if it is planar and respects the edge orientations of G. In this paper we give a polynomial-time algorithm to check whether a given HV -restricted plane graph (i.e., a planar graph with a fixed combinatorial embedding) admits a good orthogonal drawing preserving the input embedding, which settles an open question posed by Manuch, Patterson, Poon and Thachuk (GD 2010). We then examine HV -restricted planar graphs (i.e., when the embedding is not fixed). Here we completely characterize the 2-connected maximum-degree-three HV-restricted outerplanar graphs that admit good orthogonal drawings.
January 8, 2014 (E2-553)
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras.

Abstract. Consider a sliding camera that travels back and forth along an orthogonal line segment s inside an orthogonal polygon P with n vertices. The camera can see a point p inside P if and only if there exists a line segment containing p that crosses s at a right angle and is completely contained in P. In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. In this paper, we give an O(n^{5/2})-time (7/2)-approximation algorithm to the MSC problem on any simple orthogonal polygon with n vertices, answering a question posed by Katz and Morgenstern (2011). To the best of our knowledge, this is the first constant-factor approximation algorithm for this problem.
September 11, 2013 (E2-553)
Research discussion
Coordinated by : Dr. Robert Fraser and Saeed Mehrabi
Discussion topic : Selected papers from CCCG, WADS and MFCS 2013.
September 4, 2013 (E2-553)
Research discussion
Coordinated by : Mohammad Abdul Wahid
Discussion topic : Local Geometric Routing Algorithms for Edge-Augmented Planar Graphs (Thesis defense practice).

Abstract. A wireless ad-hoc network can be modeled as a geometric graph G = (V, E), where V is the set of vertices and E is the set of edges. Each node in the wireless ad-hoc network corresponds to a vertex in V and two vertices share an edge (u, v) in E, if the two corresponding nodes in the network lie within each other's transmission ranges. Any two nodes in a wireless ad-hoc network communicate with each other by sending messages. However, wireless ad-hoc networks do not have any fixed infrastructure. So, it requires routing algorithms that uses only local neighborhood relationship. Given a geometric graph G and a source-target pair {s, t} in the set V, a local geometric routing algorithm is to find a route from s to t using only local neighborhood relationship. This thesis proposes a local geometric routing algorithm that uses only single state bit as message overhead and guarantees delivery of messages in three different classes of edge-augmented planar graphs: convex subdivisions, quasi planar convex subdivisions (allow some augmented edges on a spanning convex subdivision) and 2-augmented triangulations (allow some augmented edges on a spanning triangulation). The proposed algorithm is origin-oblivious (does not require the knowledge of origin vertex s) and predecessor-oblivious (does not require the knowledge of predecessor vertex).
April 24, 2013 (E2-553)
Research discussion
Coordinated by : Mohammad Abdul Wahid
Discussion topic : Based on the paper 'A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks' - by Chun, Shioura, Tien, and Tokuyama, ALGOSENSORS 2012, LNCS 7718, p54-65, 2013.
April 10, 2013 (E2-553)
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Modelling Interference in Wireless Networks using Geometric Graphs.

Abstract. Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum interference. In this talk I will discuss recent geometric graph models for representing interference in ad hoc and sensor wireless networks, along with corresponding algorithmic and complexity results for the interference minimization problem.
April 3, 2013 (E2-553)
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Chromatic Art Gallery Problem.

Abstract. In the art gallery problem, we aim to guard a polygon with minimum number of point guards. The visibility regions of two guards overlap if there exists at least one point inside the polygon that is visible to both guards. In the chromatic art gallery problem, the goal is to color the guards with minimum number of colors such that every two guards whose visibility regions overlap receive different colors. Note that we aim to minimize the number of colors, not the number of guards. This problem was first studied due to its natural application to robot navigation. In this talk, I will describe two variants of the chromatic art gallery problem and present the current results on this problem. I will conclude with some open problems and directions for future work.
February 27, 2013 (E2-553)
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : On Graphs that are not PCGs.

Abstract. Let T be an edge weighted tree and let d_min, d_max be two nonnegative real numbers. Then the pairwise compatibility graph (PCG) of T is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent in G if and only if the weighted distance between their corresponding leaves in T is in the interval [d_min, d_max]. Similarly, a given graph G is a PCG if there exist suitable T, d_min, d_max, such that G is a PCG of T. Yanhaona, Bayzid and Rahman proved that there exists a graph with 15 vertices that is not a PCG. On the other hand, Calamoneri, Frascaria and Sinaimeri proved that every graph with at most seven vertices is a PCG. In this paper we construct a graph of eight vertices that is not a PCG, which strengthens the result of Yanhaona, Bayzid and Rahman, and implies optimality of the result of Calamoneri, Frascaria and Sinaimeri. We then construct a planar graph with sixteen vertices that is not a PCG. Finally, we prove a variant of the PCG recognition problem to be NP-complete.
February 13, 2013 (E2-553)
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Succinct Dominance Range Reporting.
January 30, 2013 (E2-553)
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Cycle counting: the next generation.

Abstract. It is a #P-complete problem to find the number of subgraphs of a given labelled graph that are cycles. Practical work on this problem splits into two streams: there are applications for counting cycles in large numbers of small graphs (for instance, all 12.3 million graphs with up to ten vertices) and software to serve that need; and there are applications for counting the cycles in just a few large graphs (for instance, hypercubes). Existing automated techniques work very well on small graphs. In this talk I review my own and others' work on large graphs, where the existing results have until now required a large amount of human participation, and I discuss an automated system for solving the problem in large graphs.
January 16, 2013 (E2-553)
Research discussion
Coordinated by : Dr. Robert Fraser
Discussion topic : The Discrete Unit Disk Cover Problem.

Abstract. Given a set P of n points and a set D of m unit radius disks in the plane, the Discrete Unit Disk Cover (DUDC) problem is to find a set D'\subset D of minimum cardinality such that D' covers P. There have been a number of approximation algorithms which have appeared in the past decade which provide increasingly better approximation factors for DUDC. In this talk we will look at a few of these approaches and some specialized versions of the DUDC problem.
October 12, 2012
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Touching triangle representations (based on a Graph Drawing 2012 paper).
September 21, 2012
Research discussion
Coordinated by : Mohammad Abdul Wahid
Discussion topic : Discussion on selected papers form CCCG 2011.
August 3, 2012
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Thesis defense practice.

Abstract. A point-set embedding of a planar graph G with n vertices on a set S of n points on the Euclidean plane is a planar drawing of G, where each vertex is mapped to a distinct point of S, each edge is drawn as a straight line segment and no two edges cross except possibly at their endpoints. In this thesis, we prove that the point-set embeddability problem is NP-complete for 3-connected planar graphs, answering an open question posed by Cabello. We give an O(n log^3 n)-time algorithm for testing point-set embeddability of plane 3-trees, improving the O(n^{4/3+e})-time algorithm of Moosa and Rahman. We prove that no set of 24 points can support all planar 3-trees with 24 vertices, which partially answers a question posed by Koborouv. We then show that every plane 3-tree with n vertices admits a 2-bend point-set embedding on any set of n points in general position in O(W^2) area, where W is the length of the side of the smallest axis parallel square that encloses S. Finally, we give a polynomial-time algorithm for testing convex point-set embeddability of klee graphs and devise a fixed-parameter tractable algorithm for testing convex point-set embeddability.
July 18, 2012
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Thesis defense practice.

Abstract. We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We de?ne two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.
E2-553, 2:30 pm, June 29, 2012
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Range minority queries in linear space.

Abstract. We consider range queries in arrays that search for low-frequency elements: least frequent elements and alpha-minorities. An alpha-minority of a query range has multiplicity no greater than an alpha fraction of the elements in the range. Our data structure for the least frequent element range query problem requires O(n) space, O(n^(3/2)) preprocessing time, and O(sqrt(n)) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the alpha-minority range query problem requires O(n) space, supports queries in O(1/alpha) time, and allows alpha to be specified at query time. Joint work with Timothy Chan, Stephane Durocher, and Bryan Wilkinson; to be presented at SWAT 2012.
E2-553, 2:30 pm, June 15, 2012
Research discussion
Coordinated by : Mohammad Abdul Wahid
Discussion topic : Cancelled.
E2-553, 2:30 pm, June 8, 2012
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Fonts and character databases for Han-script languages.

Abstract. More than one person in six speaks some form of Chinese as their first language. Mandarin alone accounts for most of that, and is globally the most popular with more than twice as many native speakers as the next most popular (Spanish and English, nearly tied). If we include other languages written in the Han script ('Chinese characters'), the proportion becomes one fifth of humanity, with most of those added being the native speakers of Japanese. The entire population of Han-script users including non-native speakers is bigger still. It is imperative that computers be able to process text in these languages, but doing so involves unique challenges. In this talk I will survey the Han script in general for an English-speaking computer science and computational geometry audience, and my own and others' work on fonts and character databases for this writing system.
E2-553, 2:30 pm, Friday, May 25, 2012
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number.

Abstract. The stabbing number of a partition of a rectilinear polygon P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment contained in P. We consider the problem of finding a rectangular partition with minimum stabbing number for a given rectilinear polygon P. First, we impose a conforming constraint on partitions: every vertex of every rectangle in the partition must lie on the polygon\92s boundary. We show that finding a conforming rectangular partition of minimum stabbing number is NP-hard for rectilinear polygons with holes. We present a rounding method based on a linear programming relaxation resulting in a polynomial-time 2-approximation algorithm. We give an O(n log n)-time algorithm to solve the problem exactly when P is a histogram (some edge in P can see every point in P) with n vertices. Next we relax the conforming constraint and show how to extend the first linear program to achieve a polynomial-time 2-approximation algorithm for the general problem, improving the approximation factor achieved by Abam, Aronov, de Berg, and Khosravi (ACM SoCG 2011).
E2-553, 3:00 pm, Thursday, May 24, 2012
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Non-Parametric Data Estimation of Pointsets using Subsets.

Abstract. We present a novel non-parametric method of simplifying polygonal lines and use this method on functional data as a statistical estimator of structure within polygonal lines and thereby eliminating sampling noise. This is joint work Alexandre Leblanc, Matthew Skala, and Stephane Durocher.
April 13, 2012
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Bounding Interference in Wireless Ad Hoc Networks.
March 30, 2012
Research discussion
Coordinated by : Mohammad Abdul Wahid
Discussion topic : Discrete Piercing Set Problem (based on a CCCG 2011 paper).
March 16, 2012
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Counting Graph Cycles.
March 2, 2012
Research discussion
Coordinated by : Dr. Helen Cameron
Discussion topic : Non-Blocking Binary Search Trees (PODC 2010).
February 10, 2012
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Geometric Placement Problems.
January 27, 2012
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : On the Hardness of Point-Set Embeddability.
January 13, 2012
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Kabaddi (based on a CCCG 2010 paper).
December 7, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Range minimum query data structure. ( Reference Paper ).
November 23, 2011
Research discussion
Coordinated by : Dr. Majid Khabbazian
Discussion : Wormhole attacks in wireless ad hoc networks.
October 26, 2011
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Compaction of a Drawing based on a GD 2011 paper .
October 12, 2011
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Measurements in Manufacturing and Their Relationship to Facility Location.
September 28, 2011
Research discussion
Coordinated by : CCCG 2011 Attendees (Lab Members)
Discussion topic : Discussion on selected papers form CCCG 2011.
September 14, 2011
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Embedding Plane 3-Trees in R2 and R3.
August 24, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Projection Median of a Set of Points.
July 27, 2011
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Realizing Site Permutations.
June 22, 2011
Research discussion
Coordinated by : Dr. Helen Cameron
Discussion topic : Hazard Pointers and Memory Reclamation.
June 08, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Recurrence Relation.
May 25, 2011
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Succinct Data Structures for Rank and Select on Binary Strings (Notes).
April 20, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Paper discussion.
April 6, 2011
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Computing Optimal Detour.
March 23, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Recent developments on the range mode query.
March 9, 2011
Research discussion
Coordinated by : Dr. Majid Khabbazian
Discussion topic : Broadcasting in ad hoc wireless networks.
February 23, 2011
Research discussion
Coordinated by : Dr. Matthew Skala
Discussion topic : Counting and characterizing distance permutations.
February 9, 2011
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Greg Aloupis' survey on Geometry of Data Depth.
January 26, 2011
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Local Routing Algorithms.
January 12, 2011
Research discussion
Coordinated by : Saeed Mehrabi
Discussion topic : Online Coloring of Interval and Co-Interval Graphs - An Overview.
December 3
Research discussion
Coordinated by : Debajyoti Mondal
Discussion topic : Drawings of Planar Graphs.
November 19
Research discussion
Coordinated by : Dr. Helen Cameron
Discussion topic : Concurrent Trees.
October 29
Research discussion
Coordinated by : Dr. Jason Morrison
Discussion topic : Registration of semi-rigid bodies of points: Applications to RSA.
October 15
Research discussion
Coordinated by : Dr. Stephane Durocher
Discussion topic : Linear-Space Static Data Structures for Range Mode Query in Arrays.