9:00  TB 360  Burning the Medial Axis Erin Wolf Chambers (Invited talk) Initially proposed by Blum in 1967, the medial axis of a shape consists of the union of all centers of maximally inscribed balls. The medial axis is one of the most commonly used tools for understanding shape, as it is homotopy equivalent to the original object, has codimension one, and is centrally located. In addition, it is used as a component in building skeletons that are of smaller dimension than the original object, but which capture the shape in a more compact but still useful representation. However, the medial axis is unstable to perturbations; even small changes in the boundary of the shape result in large changes in the medial axis. Methods for pruning the medial axis are usually guided by some measure of significance, with considerable work done for both 2 and 3 dimensional shapes. However, the majority of significance measures over the medial axis are locally defined and hence unable to capture more global features, or are difficult to compute and sensitive to perturbations on the boundary. In general, there are no skeletons which provably capture the correct topology, are central to the object, are always result in a curve skeleton for a 3dimensional input. In this talk, I will present recent work done in 2d and 3d to compute new significance measures on the medial axis. In 2d, the extended distance function (EDF), also called the burn time, was recently developed by Liu et al., as well as related measures such as erosion thickness and weighted EDF. The EDF function was later generalized to the burn time function for 3 dimensional shapes, yielding both a mathematical framework for quantifying shape as well as an algorithm for approximating this function for a union of balls, which are commonly used for surface reconstruction and approximation. In 3d, this also allows us to develop a definition of topologically accurate 1dimensional skeletons. These measures give practical methods for differentiating boundary noise from primary features, and can be used for shape alignment and recognition. In addition, there is both practical and theoretical evidence that these measures are robust under certain types of noise in the boundary, unlike the medial axis itself. 
10:00   Break 
10:30  Session 3ATB 360   The mostlikely skyline problem for stochastic points Akash Agrawal, Yuan Li, Jie Xue and Ravi Janardan.
For a set $O$ of $n$ points in $\mathbb{R}^d$, a skyline is a subset of points where no point is dominated by any other point of $O$. Suppose that each point $o_i$ in $O$ has an associated probability of existence $p_i$ in $(0,1]$. The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in $\mathbb{R}^d$, $d \geq 3$, the problem is NPhard and that the desired skyline cannot even be wellapproximated in polynomialtime unless P=NP. In $\mathbb{R}^2$, an optimal $O(n \log n)$time and $O(n)$space algorithm is given.  Visibility Testing and Counting for Uncertain Segments Mohammad Ali Abam, Sharareh Alipour, Mohammad Ghodsi and Mohammad Mahdian.
We study two wellknown planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set $S$ of $n$ segments in $\mathbb{R}^2$, and we would like to preprocess $S$ so that we can quickly answer queries of the form: is the given query segment $s \in S$ visible from the given query point $q \in \mathbb{R}^2$ (for visibility testing) and how many segments in $S$ are visible from the given query point $q \in \mathbb{R}^2$ (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment $s \in S$ is visible from a given query point $q$ and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in $S$ that are visible from a query point $q$. We first show that PVTP is $\#P$complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that the problem is solvable in $O(n\log n)$ time. Using this, together with a few old tricks, we can show that one can preprocess $S$ in $O(n^5\log n)$ time into a data structure of size $O(n^4)$ so that PVTP queries can be answered in $O(\log n)$ time. Our algorithm for PVTP combined with linearity of expectation gives an $O(n^2\log n)$ time algorithm for PVCP. We also give a faster 2approximation algorithm for this problem.  NearestNeighbor Search Under Uncertainty Boris Aronov, John Iacono and Khadijeh Sheikhan.
We study the problem of NearestNeighbor Searching under locational uncertainty. Here, an uncertain query or site consists of a set of points in the plane, and their distance is defined as distance between the two farthest points within them. In $L_\infty$ metric, we present an algorithm with $O(n\log^2n+s)$ preprocessing time, $O(n\log n)$ space, and $O(\log^2n+k)$ query time, where $s$ is the total number of site points, $n$ is the number of sites, and $k$ is the size of the query. We also propose a $\sqrt{2}$approximation algorithm for the $L_2$ version of the problem.

 Session 3BTB 340   A Seed Placement Strategy for Conforming Voronoi Meshing Ahmed Abdelkader, Chandrajit Bajaj, Mohamed Ebeida and Scott Mitchell.
We show how to place a set of seed points such that a given piecewise linear complex is the union of some faces in the resulting Voronoi diagram. The seeds are placed on sufficiently small spheres centered at input vertices and are arranged into little circles around each halfedge where every seed is mirrored across the associated triangle. The Voronoi faces common to the seeds of such arrangements yield a mesh conforming to the input complex. If the input contains sharp angles, then additional seeds are needed, analogous to nonobtuse refinement. Finally, we propose local optimizations to reduce the number of seeds and output facets.  On Compatible Triangulations with a Minimum Number of Steiner Points Anna Lubiw and Debajyoti Mondal.
Two polygons are compatible if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations  for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible $n$vertex polygonal regions can be extended to compatible triangulations by adding $O(n^2)$ Steiner points. Furthermore, $\Omega(n^2)$ Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka "2D shape animation". An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most $k$ Steiner points. In this paper we prove the problem to be NPhard for polygons with holes. The question remains open for simple polygons.  Planarity Preserving Augmentation of Topological and Geometric Plane Graphs to Meet Parity Constraints Israel Aldana Galván, José Luis Álvarez Rebollar, Juan Carlos CatanaSalazar, Erick Solís Villarreal, Jorge Urrutia and Carlos Bruno Velarde Valázquez.
We introduce the augmentation problem to meet parity constraints in topological and geometric plane graphs. We show a family of topological plane graphs such that any augmentation leaves at least $2n/5$ vertices without meeting their parity constraints, and a family of geometric plane trees such that any augmentation leaves at least $n/10$ vertices without meeting their parity constraints. We prove that the problem of adding a minimum number of edges to plane geometric graphs is NPComplete. When the input graph is a topological tree finding a minimum set of edges that needed to be added to meet a parity constrain is solvable in $O(n)$ time and $O(1)$ space. We also establish a lower bound of $11n/15$ on the number of necessary edges to augment a topological graph when the graph is augmentable, and a lower bound of $6n/11$ on the number of necessary edges to augment a geometric tree when the tree is also augmentable.

11:30   Lunch (on your own) 
12:00  TB 340  Industry talk with ShopifyCome join us for lunch and learn from one of Shopify’s data engineers about what it is like to work at Shopify and how computational geometry can be applied in industry. Shopify is the leading cloudbased, multichannel commerce platform designed for small and mediumsized businesses. Merchants can use the software to design, set up, and manage their stores across multiple sales channels, including web, mobile, social media, marketplaces, brickandmortar locations, and popup shops. The Shopify platform was engineered for reliability and scale, making enterpriselevel technology available to businesses of all sizes. Shopify currently powers over 400,000 businesses in approximately 175 countries and is trusted by brands such as Tesla, Red Bull, Nestle, GE, Kylie Cosmetics, and many more. 
13:30  Session 4ATB 360   Interference Minimization in kConnected Wireless Networks Stephane Durocher and Sahar Mehrpour.
Given a set of positions for wireless nodes, the $k$connected interference minimization problem seeks to assign a transmission radius to each node such that the resulting network is $k$connected and the maximum interference is minimized. We show there exist sets of $n$ points on the line for which any $k$connected network has maximum interference $\Omega(\sqrt{kn})$. We present polynomialtime algorithms that assign transmission radii to any given set of $n$ nodes to produce a $k$connected network with maximum interference $O(\sqrt{kn})$ in one dimension and $O(\min \{ k\sqrt{n}, k\log\lambda \})$ in two dimensions, where $\lambda$ denotes the ratio of the longest to shortest distances between any pair of nodes.  Optimal Orientation of Symmetric Directional Antennas Amirmahdi Ahmadinejad, Fatemeh Baharifard, Khadijeh Sheikhan and Hamid ZarrabiZadeh.
In this paper, we study the problem of optimal orientation of directional antennas in the symmetric model of communication. We propose an optimal algorithm to find the minimum radius and the orientation of antennas, when antennas are placed on a set $P$ of points on a line, and each antenna has angle less than $\pi$. We show that the connected graph induced by this optimal orientation is a 7hop spanner with respect to the unit disk graph of $P$. Moreover, we present a deterministic local routing algorithm that is guaranteed to find a path between any pair of antennas in the communication graph whose number of edges is at most 7 times the number of edges between that pair in the unit disk graph.  Range Assignment of BaseStations Maximizing Coverage Area without Interference Ankush Acharyya, Minati De and Subhas C. Nandy.
This note is a study on the problem of maximizing the sum of area of nonoverlapping disks centered at a set of given points in $I\!\!R^2$. If the points of $P$ are placed on a straightline, then the problem is solvable in polynomial time. Eppstein [CCCG, pages 260–265, 2016] proposed an $O(n^\frac{3}{2})$ time algorithm, for maximizing the sum of radii of nonoverlapping balls or disks when the points are arbitrarily placed on a plane. We show that the solution to this problem gives a $2$approximation solution for the area maximization problem by nonoverlapping disks or balls. We also present simulation results. Finally, we propose a PTAS for our problem.

 Session 4BTB 340   Nonoverlapping Gridaligned Rectangle Placement for High Value Areas Stephen Rowe, Christopher Valicka, Scott Mitchell and Simon Zou.
We consider heuristic and optimal solutions to a discrete geometric bin packing problem that arises in a resource allocation problem. An imaging sensor is assigned to collect data over a large area, but some subregions are more valuable than others. To capture these highvalue regions with higher fidelity, we can assign some number of nonoverlapping rectangular subsets, called “subfootprints.” The sensor image is partitioned into squares called “chips”, and each chip is further partitioned into pixels. Pixels may have different values. Subfootprints are restricted to rectangular collections of chips, but we are free to choose different rectangle heights, widths, and areas. We seek the optimal arrangement over the family of possible rectangle shapes and sizes. We provide a mixedinteger linear program optimization formulation, as well as a greedy heuristic, to solve this problem. For the metaproblem, we have some freedom to align the chip boundaries to different pixels. However, it is too expensive to solve the optimization formulation for each alignment. However, we show that the greedy heuristic can inform which pixel alignments are worth solving the optimization over. We use a variant of $k$means clustering to group greedy solutions by their transport shapesimilarity. For each cluster, we run the optimization problem over the greedy layout with the highest value. In practice this efficiently explores the geometric configuration space, and produces solutions close to the global optimum. We show a contrived example using surveillance of the Mississippi River. Our software is available as opensource in the Github repository “GeoPlace.”  Packing BoundaryAnchored Rectangles Therese Biedl, Ahmad Biniaz, Anil Maheshwari and Saeed Mehrabi.
In this paper, we study the boundaryanchored rectangle packing problem in which we are given a set $P$ of points on the boundary of an axisaligned square $Q$. The goal is to find a set of disjoint axisaligned rectangles in $Q$ such that each rectangle is anchored at some point in $P$, each point in $P$ is used to anchor at most one rectangle, and the total area of the rectangles is maximized. We show how to solve this problem in lineartime in the number of points of $P$, provided that the points of $P$ are given in sorted order along the boundary of $Q$. The solvability of the general version of this problem, in which the points of $P$ can also lie in the interior of $Q$, in polynomialtime, is still open.  Dominating Set of Rectangles Intersecting an Inclined Line Supantha Pandit.
We study the minimum dominating set problem using axisparallel rectangles and unit squares on the plane. These geometric objects are constrained to be intersected by a line which makes an angle with the $x$axis. For axisparallel rectangles, we prove that this problem is NPcomplete. When the objects are axisparallel unit square, we give a polynomial time algorithm. For unit squares which touches the inclined line at a single point from either side of the inclined line, we give an $O(n\log n)$ time algorithm.

14:30   Break 
15:00  Session 5ATB 360   On Guarding Orthogonal Polygons with Bounded Treewidth Therese Biedl and Saeed Mehrabi.
There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see an entire rectangle, or along a staircase, or along a orthogonal path with at most $k$ bends. In this paper, we study all these guarding models in the special case of orthogonal polygons that have bounded treewidth in some sense. Exploiting algorithms for graphs of bounded treewidth, we show that the problem of finding the minimum number of guards in these models becomes lineartime solvable in polygons of bounded treewidth.  Beacon Coverage in Orthogonal Polyhedra José Luis ÁlvarezRebollar, Israel AldanaGalván, Juan Carlos CatanaSalazar, Jesús Nestaly MarínNevárez, Erick SolísVillarreal, Jorge Urrutia and Carlos Bruno Velarde.
We consider a variant of the Art Galllery Problem in orthogonal polygons and orthogonal polyhedra using beacons as guards. A beacon is a device that attracts objects toward itself within a given domain. A beacon $b$ covers a point if when a beacon attracts it, it reaches $b$. In this paper, we prove that there exist orthogonal polyhedra that cannot be covered even if we place a beacon at each of its vertices. We also give another example for covering the exterior of an orthogonal polyhedra. We also study the beacon coverage problem in orthogonal polyhedra, by extending the notion of vertex beacons to edge beacons. We prove that $e/12$ edge beacons are always sufficecient while $e/21$ edge beacons are sometimes necessary to cover any orthogonal polyhedron. We also prove that $e/6$ edge beacons are always sufficient to cover both the interior and the exterior of any orthogonal polyhedra.  Discrete Surveillance Tours in Polygonal Domains Elmar Langetepe, Bengt J. Nilsson and Eli Packer.
The shortest watchman route of a polygon is the shortest closed tour that sees all points of an environment. A reasonable extension of this concept is to require that the tour minimizes the hiding time of the points in the environment, i.e., the maximum time during which any points is not seen by the agent following the tour at unit speed. We call such tours surveillance routes. It is known that the shortest watchman route is a 2approximation for the best surveillance route in any simple polygon and any metric and that computing the optimum weighted discrete version of the surveillance route in a simple polygon is NPhard, even for two weight values. We show a linear time $3/2$approximation algorithm for the optimum surveillance tour problem in rectilinear polygons using the $L_1$ metric. In addition, we present a $w_{\max}^{\frac{O(1)}{\sqrt{\log w_{\max}}}}$approximation algorithm for the optimum weighted discrete surveillance route in a simple polygon with weight values in the range $[1,w_{\max}]$. We observe that the above complexity function grows asymptotically slower than any function $O(\sqrt[k]{w_{\max}})$, for any constant $k$.  Guarding Monotone Polygons with HalfGuards Matt Gibson, Erik Krohn and Matthew Rayford.
We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside a monotone polygon. We provide a polynomialtime 4approximation algorithm for a version of the problem where we wish to point guard the vertices of the polygon. We then extend this algorithm and provide a $O(1)$approximation to point guard the boundary of the polygon and ultimately the entire polygon.

 Session 5BTB 340   Sharing a pizza: bisecting masses with two cuts Luis Barba and Patrick Schnider.
Assume you have a pizza consisting of four ingredients (e.g. bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the wellknown HamSandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines. That is, there exist two oriented lines with the following property: let $R^+_1$ be the region of the plane that lies to the positive side of both lines and let $R^+_2$ be the region of the plane that lies to the negative side of both lines. Then $R^+=R^+_1\cup R^+_2$ contains exactly half of each mass distribution. Additionally, we prove that five mass distributions in $\mathbb{R}^3$ can be simultaneously bisected by two planes.  Balanced $k$Center Clustering When $k$ Is A Constant Hu Ding.
The problem of constrained $k$center clustering has attracted significant attention in the past decades. In this paper, we study balanced $k$center cluster where the size of each cluster is constrained by the given lower and upper bounds. The problem is motivated by the applications in processing and analyzing largescale data in high dimension. We provide a simple nearly linear time $4$approximation algorithm when the number of clusters $k$ is assumed to be a constant. Comparing with existing method, our algorithm improves the approximation ratio and significantly reduces the time complexity. Moreover, our result can be easily extended to any metric space.  2D Closest Pair Problem: A Closer Look Ovidiu Daescu and Ka Yaw Teo.
A closer look is taken at the wellknown divideandconquer algorithm for finding the closest pair of a set of points in the plane under the Euclidean distance. An argument is made that it is sufficient, and sometimes necessary, to check only the next three points following the current point associated with the $y$sorted array in the combine phase of the algorithm.  Supporting Ruled Polygons Nicholas Cavanna, Marc Khoury and Donald Sheehy.
We explore several problems related to ruled polygons. Given a ruling of a polygon $P$, we consider the Reeb graph of $P$ induced by the ruling. We define the Reeb complexity of $P$, which roughly equates to the minimum number of points necessary to support $P$. We give asymptotically tight bounds on the Reeb complexity that are also tight up to a small additive constant. When restricted to the set of parallel rulings, we show that the Reeb complexity can be computed in polynomial time.

18:00  Cornerstone Bar and Grill  Dinner 
20:00  National Gallery of Canada  Kumo Awakens 