Author name cluster

Stephane Durocher

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

I&C Journal 2026 Journal Article

Computing conforming partitions with low stabbing number for rectilinear polygons

Therese Biedl
Stephane Durocher
Debajyoti Mondal
Rahnuma Islam Nishat
Bastien Rivier

A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i. e. , all corners of all rectangles must lie on the boundary of P). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P. In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP -hard, which strengthens a previously known hardness result [Durocher & Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP. In contrast, we give (i) an O ( n log ⁡ n ) -time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position.

Details DOI

TCS Journal 2025 Journal Article

Approximation algorithms for minimum ply covering of points with unit squares and unit disks

Stephane Durocher
J. Mark Keil
Debajyoti Mondal

Given a set P of points and a set U of geometric objects 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 objects that share a common intersection, called the minimum ply cover number of P with U. Biedl et al. (2021) [9] showed that for both unit squares and unit disks, determining the minimum ply cover number for a set of points is NP-hard. They gave polynomial-time 2-approximation algorithms for the special case when the minimum ply cover number is constant, and asked whether there exists polynomial-time O ( 1 ) -approximation algorithms for these problems. In this paper, we settle the question posed by Biedl et al. by providing polynomial-time O ( 1 ) -approximation algorithms for the minimum ply cover problem for both unit squares and unit disks.

Details DOI

TCS Journal 2019 Journal Article

A simple linear-space data structure for constant-time range minimum query

Stephane Durocher
Robby Singh

We revisit the range minimum query problem and present a new O ( n ) -space data structure that supports range minimum queries in O ( 1 ) time. The goal is to construct a static data structure that efficiently supports range minimum queries on a given list A [ 0: n − 1 ] of n items drawn from a totally ordered set. Each range minimum query consists of an input pair of indices ( i, j ) for which the minimum element of the subarray A [ i: j ] must be returned. Although previous data structures exist whose asymptotic bounds match ours, our goal is to introduce a new solution that is simple, intuitive, and practical without increasing asymptotic costs for query time or space. We analyze our new data structure theoretically and practically, the latter through an evaluation of its performance relative to implementations of four of the top range minimum query data structures.

Details DOI

TCS Journal 2019 Journal Article

A time–space trade-off for computing the k-visibility region of a point in a polygon

Yeganeh Bahoo
Bahareh Banyassady
Prosenjit K. Bose
Stephane Durocher
Wolfgang Mulzer

Let P be a simple polygon with n vertices, and let q ∈ P be a point in P. Let k ∈ { 0, …, n − 1 }. A point p ∈ P is k-visible from q if and only if the line segment pq crosses the boundary of P at most k times. The k-visibility region of q in P is the set of all points that are k-visible from q. We study the problem of computing the k-visibility region in the limited workspace model, where the input resides in a random-access read-only memory of O ( n ) words, each with Ω ( log ⁡ n ) bits. The algorithm can read and write O ( s ) additional words of workspace, where s ∈ N is a parameter of the model. The output is written to a write-only stream. Given a simple polygon P with n vertices and a point q ∈ P, we present an algorithm that reports the k-visibility region of q in P in O ( c n / s + c log ⁡ s + min ⁡ { ⌈ k / s ⌉ n, n log ⁡ log s ⁡ n } ) expected time using O ( s ) words of workspace. Here, c ∈ { 1, …, n } is the number of critical vertices of P for q where the k-visibility region of q may change. We generalize this result for polygons with holes and for sets of non-crossing line segments.

Details DOI

TCS Journal 2019 Journal Article

Polygon simplification by minimizing convex corners

Yeganeh Bahoo
Stephane Durocher
J. Mark Keil
Debajyoti Mondal
Saeed Mehrabi
Sahar Mehrpour

Let P be a polygon with r > 0 reflex vertices and possibly with holes and islands (i. e. , components of the polygon inside holes). A subsuming polygon of P is a polygon P ′ such that P ⊆ P ′, each connected component R of P is a subset of a distinct connected component R ′ of P ′, and the reflex corners of R coincide with those 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, and posed an open problem to determine the computational complexity of computing subsuming polygons with the minimum number of convex vertices. In this paper, we prove that the problem of computing an optimal subsuming polygon is NP-hard (but the complexity remains open for simple polygons; i. e. , polygons without holes). Our NP-hardness result holds even when the subsuming chains are restricted to have constant length and lie on the arrangement of lines determined by the edges of the input polygon. We show that this restriction makes the problem polynomial-time solvable for simple polygons.

Details DOI

TCS Journal 2017 Journal Article

Computing conforming partitions of orthogonal polygons with minimum stabbing number

Stephane Durocher
Saeed Mehrabi

Let P be an orthogonal polygon with n vertices. A partition of P into rectangles is called conforming if it results from cutting P along a set of interior-disjoint line segments, each having both endpoints on the boundary of P. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside P. In this paper, we consider the problem of finding a conforming partition of P with minimum stabbing number. We first give an O ( n log ⁡ n ) -time algorithm to solve the problem when P is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP-hard if P is allowed to have holes.

Details DOI

TCS Journal 2015 Journal Article

Complexity of barrier coverage with relocatable sensors in the plane

Stefan Dobrev
Stephane Durocher
Mohsen Eftekhari
Konstantinos Georgiou
Evangelos Kranakis
Danny Krizanc
Lata Narayanan
Jaroslav Opatrny

We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area of fixed range centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: (i) the feasibility of barrier coverage, (ii) the problem of minimizing the largest relocation distance of a sensor (MinMax), and (iii) the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the MinMax problem is shown to be strongly NP-complete for sensors with arbitrary ranges. We also study the case when sensors are restricted to use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is strongly NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O ( n 3 / 2 ) algorithm for a natural special case of this last problem.

Details DOI

TCS Journal 2015 Journal Article

Low space data structures for geometric range mode query

Stephane Durocher
Hicham El-Zein
J. Ian Munro
Sharma V. Thankachan

Let S be a set of n points in d dimensions such that each point is assigned a color. Given a query range Q = [ a 1, b 1 ] × [ a 2, b 2 ] × … × [ a d, b d ], the geometric range mode query problem asks to report the most frequent color (i. e. , a mode) of the multiset of colors corresponding to points in S ∩ Q. When d = 1, Chan et al. (2012) [1] gave a data structure that requires O ( n + ( n / Δ ) 2 / w ) words and supports range mode queries in O ( Δ ) time for any Δ ≥ 1, where w = Ω ( log ⁡ n ) is the word size. Chan et al. also proposed a data structures for higher dimensions (i. e. , d ≥ 2 ) with O ( s n + ( n / Δ ) 2 d ) words and O ( Δ ⋅ t n ) query time, where s n and t n denote the space and query time of a data structure that supports orthogonal range counting queries on the set S. In this paper we show that the space can be improved without any increase to the query time, by presenting an O ( s n + ( n / Δ ) 2 d / w ) -word data structure that supports orthogonal range mode queries on a set of n points in d dimensions in O ( Δ ⋅ t n ) time, for any Δ ≥ 1. When d = 1, these space and query time costs match those achieved by the current best known one-dimensional data structure.

Details DOI

TCS Journal 2015 Journal Article

On graphs that are not PCGs

Stephane Durocher
Debajyoti Mondal
Md. Saidur Rahman

Let T be an edge-weighted tree and let d min, d max be two nonnegative real numbers. 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.

Details DOI

TCS Journal 2015 Journal Article

Searching on a line: A complete characterization of the optimal solution

Prosenjit Bose
Jean-Lou De Carufel
Stephane Durocher

We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. Prior to this work, only asymptotic bounds were known for the optimal competitive ratio achievable by any search strategy in the worst case. We present the first tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given bounds on D, along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique. We characterize the conditions under which an optimal strategy can be computed exactly and, when it cannot, we explain how numerical methods can be used efficiently. In addition, we answer several related open questions, including the maximal reach problem, and we discuss how to generalize these results to m rays, for any m ≥ 2.

Details DOI

MFCS Conference 2013 Conference Paper

Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results

Stephane Durocher
Saeed Mehrabi 0001

Abstract Let P be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment s ⊆ P as its trajectory. The camera can see a point p ∈ P if there exists a point q ∈ s such that pq is a line segment normal to s that is completely contained in P. In the minimum-cardinality sliding cameras problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i. e. , every point in P can be seen by some sliding camera in S ) while in the minimum-length sliding cameras problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel. In this paper, we first settle the complexity of the minimum-length sliding cameras problem by showing that it is polynomial tractable even for orthogonal polygons with holes, answering a question posed by Katz and Morgenstern [9]. Next we show that the minimum-cardinality sliding cameras problem is NP -hard when P is allowed to have holes, which partially answers another question posed by Katz and Morgenstern [9].

Details

MFCS Conference 2013 Conference Paper

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

Stephane Durocher
Rahul Shah 0001
Matthew Skala
Sharma V. Thankachan

Abstract We present O ( n )-space data structures to support various range frequency queries on a given array A [0: n − 1] or tree T with n nodes. Given a query consisting of an arbitrary pair of pre-order rank indices ( i, j ), our data structures return a least frequent element, mode, or α -minority of the multiset of elements in the unique path with endpoints at indices i and j in A or T. We describe a data structure that supports range least frequent element queries on arrays in \(O(\sqrt{n / w})\) time, improving the \(\Theta(\sqrt{n})\) worst-case time required by the data structure of Chan et al. (SWAT 2012), where w ∈ Ω(log n ) is the word size in bits. We describe a data structure that supports range mode queries on trees in \(O(\log\log n \sqrt{n / w})\) time, improving the \(\Theta(\sqrt{n} \log n)\) worst-case time required by the data structure of Krizanc et al. (ISAAC 2003). Finally, we describe a data structure that supports range α -minority queries on trees in O ( α − 1 loglog n ) time, where α ∈ [0, 1] is specified at query time.

Details

I&C Journal 2013 Journal Article

Range majority in constant time and linear space

Stephane Durocher
Meng He
J. Ian Munro
Patrick K. Nicholson
Matthew Skala

Given an array A of size n, we consider the problem of answering range majority queries: given a query range [ i. . j ] where 1 ⩽ i ⩽ j ⩽ n, return the majority element of the subarray A [ i. . j ] if it exists. We describe a linear space data structure that answers range majority queries in constant time. We further generalize this problem by defining range α-majority queries: given a query range [ i. . j ], return all the elements in the subarray A [ i. . j ] with frequency greater than α ( j − i + 1 ). We prove an upper bound on the number of α-majorities that can exist in a subarray, assuming that query ranges are restricted to be larger than a given threshold. Using this upper bound, we generalize our range majority data structure to answer range α-majority queries in O ( 1 α ) time using O ( n lg ( 1 α + 1 ) ) space, for any fixed α ∈ ( 0, 1 ). This result is interesting since other similar range query problems based on frequency have nearly logarithmic lower bounds on query time when restricted to linear space.

Details DOI

TCS Journal 2011 Journal Article

Reconstructing polygons from scanner data

Therese Biedl
Stephane Durocher
Jack Snoeyink

A range-finding scanner can collect information about the shape of an (unknown) polygonal room in which it is placed. Suppose that a set of scanners returns not only a set of points, but also additional information, such as the normal to the plane when a scan beam detects a wall. We consider the problem of reconstructing the floor plan of a room from different types of scan data. In particular, we present algorithmic and hardness results for reconstructing two-dimensional polygons from point-wall pairs, point-normal pairs, and visibility polygons. The polygons may have restrictions on topology (e. g. , to be simply connected) or geometry (e. g. , to be orthogonal). We show that this reconstruction problem is NP-hard under most models, but that some restrictive assumptions do allow polynomial-time reconstruction algorithms.

Details DOI

TCS Journal 2011 Journal Article

Untangled monotonic chains and adaptive range search

Diego Arroyuelo
Francisco Claude
Reza Dorrigiv
Stephane Durocher
Meng He
Alejandro López-Ortiz
J. Ian Munro
Patrick K. Nicholson

We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data that is better than the worst case (Demaine et al. , 2000) [8]; in this case, data with more inherent sortedness. Given n points on the plane, the linear space data structure can answer range queries in O ( log n + k + m ) time, where m is the number of points in the output and k is the minimum number of monotonic chains into which the point set can be decomposed, which is O ( n ) in the worst case. Our result matches the worst-case performance of other optimal-time linear space data structures, or surpasses them when k = o ( n ). Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves (Munro and Suwanda, 1980) [16], in which case the query time becomes O ( k log n + m ). We also present a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, similarly directed monotonic chains in O ( k 2 n + n log n ) time.

Details DOI