56 Result(s)

Chapter and Conference Paper

Minimum Ply Covering of Points with Unit Squares

Given a set P of points and a set U of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of P with U is a subset of U that covers P and minimizes the number of squares that share a common int...

Stephane Durocher, J. Mark Keil, Debajyoti Mondal in WALCOM: Algorithms and Computation (2023)

Chapter and Conference Paper

Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon

We consider the problem of finding a geodesic disc of smallest radius containing at least k points from a set of n points in a simple polygon that has m vertices, r of which are reflex vertices. We refer to such ...

Prosenjit Bose, Anthony D’Angelo, Stephane Durocher in Algorithms and Data Structures (2023)

Chapter and Conference Paper

Cops and Robbers on 1-Planar Graphs

Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of G is the minimum number of cops ...

Stephane Durocher, Shahin Kamali… in Graph Drawing and Network Visualization (2023)

Article

On the restricted k-Steiner tree problem

Given a set P of n points in \(\mathbb {R}^2\) R ...

Prosenjit Bose, Anthony D’Angelo… in Journal of Combinatorial Optimization (2022)

Chapter and Conference Paper

Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set

Chvátal and Klincsek (1980) gave an \(O(n^3)\) O (

Stephane Durocher, J. Mark Keil, Saeed Mehrabi… in Computing and Combinatorics (2021)

Article

Computing the k-Visibility Region of a Point in a Polygon

Two points p and q in a simple polygon P are k-visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, a positive integer k, and a polygon P, we design an algorithm that...

Yeganeh Bahoo, Prosenjit Bose, Stephane Durocher… in Theory of Computing Systems (2020)

Chapter and Conference Paper

On the Restricted 1-Steiner Tree Problem

Given a set P of n points in \(\mathbb {R}^2\) and an input line ...

Prosenjit Bose, Anthony D’Angelo, Stephane Durocher in Computing and Combinatorics (2020)

Chapter and Conference Paper

Computing the k-Crossing Visibility Region of a Point in a Polygon

Two points p and q in a simple polygon P are k-crossing visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, an integer k, and a polygon P, we propose an algorithm th...

Yeganeh Bahoo, Prosenjit Bose, Stephane Durocher… in Combinatorial Algorithms (2019)

Chapter and Conference Paper

Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon

We study the problem of computing the k-visibility region in the memory-constrained model. In this model, the input resides in a randomly accessible read-only memory of O(n) words, with

Yeganeh Bahoo, Bahareh Banyassady, Prosenjit Bose… in WALCOM: Algorithms and Computation (2017)

Reference Work Entry In depth

Routing in Geometric Networks

Stephane Durocher, Leszek Gasieniec, Prudence W. H. Wong in Encyclopedia of Algorithms (2016)

Article

Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees

We present \(O(n)\) O (

Stephane Durocher, Rahul Shah, Matthew Skala, Sharma V. Thankachan in Algorithmica (2016)

Chapter and Conference Paper

Polygon Simplification by Minimizing Convex Corners

Let P be a polygon with \(r>0\) reflex vertices and possibly with holes. A subsuming polygon of P is a polygon ...

Yeganeh Bahoo, Stephane Durocher, J. Mark Keil… in Computing and Combinatorics (2016)

Article

Linear-Space Data Structures for Range Minority Query in Arrays

We consider range queries that search for low-frequency elements (least frequent elements and \(\alpha \) ...

Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson in Algorithmica (2015)

Living Reference Work Entry In depth

Routing in Geometric Networks

Stephane Durocher, Leszek Gąsieniec, Prudence W.H. Wong in Encyclopedia of Algorithms

Chapter and Conference Paper

Local Routing in Convex Subdivisions

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 ge...

Prosenjit Bose, Stephane Durocher… in SOFSEM 2015: Theory and Practice of Comput… (2015)

Chapter and Conference Paper

A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

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 sli...

Stephane Durocher, Saeed Mehrabi in Combinatorial Algorithms (2015)

Article

Linear-Space Data Structures for Range Mode Query in Arrays

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing...

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen… in Theory of Computing Systems (2014)

Chapter and Conference Paper

Drawing HV-Restricted Planar Graphs

A strict orthogonal drawing of a graph G = (V, E) in ℝ² 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-rest...

Stephane Durocher, Stefan Felsner, Saeed Mehrabi… in LATIN 2014: Theoretical Informatics (2014)