Carleton University

output

19922026

most citedObservation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC

10.9k citations

Showing 2018 · cs.CGShow all

8 papers · 2 filters

cs.CG2018

Polygon Simplification by Minimizing Convex Corners

Yeganeh Bahoo, Stephane Durocher, J. Mark Keil +3

Let $P$ be a polygon with $r > 0$ reflex vertices and possibly with holes and islands. A subsuming polygon of $P$ is a polygon $P^{'}$ such that $P \subseteq P^{'}$ , each connected compone…

cs.CG2018

Convex Polygons in Cartesian Products

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans +4

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every…

cs.CG2018

Rectilinear Shortest Paths Among Transient Obstacles

Anil Maheshwari, Arash Nouri, Jörg-Rüdiger Sack

This paper presents an optimal $Θ (n lo g n)$ algorithm for determining time-minimal rectilinear paths among $n$ transient rectilinear obstacles. An obstacle is transient if it exis…

cs.CG2018★ 3 cited

Closest-Pair Queries in Fat Rectangles

Sang Won Bae, Michiel Smid

In the range closest pair problem, we want to construct a data structure storing a set $S$ of $n$ points in the plane, such that for any axes-parallel query rectangle $R$ , the clos…

cs.CG2018

On the Spanning and Routing Ratio of Directed Theta-Four

Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill +1

We present a routing algorithm for the directed $Θ_{4}$ -graph, here denoted as the $\overrightarrow{Θ_4}}$-graph, that computes a path between any two vertices $s$ and $t$ having len…

cs.CG2018

Improved Bounds for Guarding Plane Graphs with Edges

Ahmad Biniaz, Prosenjit Bose, Aurélien Ooms +1

An "edge guard set" of a plane graph $G$ is a subset $Γ$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $Γ$ . Such a set is said to guard $G$ . W…