Source author record

Stephane Durocher

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.CO Discrete Mathematics Computer Vision Networking and Internet Architecture

Catalog footprint

Research overview

14works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A structured latent space for human body motion generation

We propose a framework to learn a structured latent space to represent 4D human body motion, where each latent vector encodes a full motion of the whole 3D human shape. On one hand several data-driven skeletal animation models exist proposing motion spaces of temporally dense motion signals, but based on geometrically sparse kinematic representations. On the other hand many methods exist to build shape spaces of dense 3D geometry, but for static frames. We bring together both concepts, proposing a motion space that is dense both temporally and geometrically. Once trained, our model generates a multi-frame sequence of dense 3D meshes based on a single point in a low-dimensional latent space. This latent space is built to be structured, such that similar motions form clusters. It also embeds variations of duration in the latent vector, allowing semantically close sequences that differ only by temporal unfolding to share similar latent vectors. We demonstrate experimentally the structural properties of our latent space, and show it can be used to generate plausible interpolations between different actions. We also apply our model to 4D human motion completion, showing its promising abilities to learn spatio-temporal features of human motion.

preprint2022arXiv

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 intersection, called the minimum ply cover number of $P$ with $U$ . Biedl et al. [Comput. Geom., 94:101712, 2020] showed that determining the minimum ply cover number for a set of points by a set of axis-parallel unit squares is NP-hard, and gave a polynomial-time 2-approximation algorithm for instances in which the minimum ply cover number is constant. The question of whether there exists a polynomial-time approximation algorithm remained open when the minimum ply cover number is $ω(1)$ . We settle this open question and present a polynomial-time $(8+\varepsilon)$ -approximation algorithm for the general problem, for every fixed $\varepsilon>0$ .

preprint2016arXiv

Relating Graph Thickness to Planar Layers and Bend Complexity

The thickness of a graph $G=(V,E)$ with $n$ vertices is the minimum number of planar subgraphs of $G$ whose union is $G$ . A polyline drawing of $G$ in $\mathbb{R}^2$ is a drawing $Γ$ of $G$ , where each vertex is mapped to a point and each edge is mapped to a polygonal chain. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of $Γ$ is the maximum number of bends per edge in $Γ$ , and the layer complexity of $Γ$ is the minimum integer $r$ such that the set of polygonal chains in $Γ$ can be partitioned into $r$ disjoint sets, where each set corresponds to a planar polyline drawing. Let $G$ be a graph of thickness $t$ . By Fáry's theorem, if $t=1$ , then $G$ can be drawn on a single layer with bend complexity $0$ . A few extensions to higher thickness are known, e.g., if $t=2$ (resp., $t>2$ ), then $G$ can be drawn on $t$ layers with bend complexity 2 (resp., $3n+O(1)$ ). However, allowing a higher number of layers may reduce the bend complexity, e.g., complete graphs require $Θ(n)$ layers to be drawn using 0 bends per edge. In this paper we present an elegant extension of Fáry's theorem to draw graphs of thickness $t>2$ . We first prove that thickness- $t$ graphs can be drawn on $t$ layers with $2.25n+O(1)$ bends per edge. We then develop another technique to draw thickness- $t$ graphs on $t$ layers with bend complexity, i.e., $O(\sqrt{2}^{t} \cdot n^{1-(1/β)})$ , where $β= 2^{\lceil (t-2)/2 \rceil }$ . Previously, the bend complexity was not known to be sublinear for $t>2$ . Finally, we show that graphs with linear arboricity $k$ can be drawn on $k$ layers with bend complexity $\frac{3(k-1)n}{(4k-2)}$ .

preprint2014arXiv

Cycle-maximal triangle-free graphs

We conjecture that the balanced complete bipartite graph $K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil}$ contains more cycles than any other $n$ -vertex triangle-free graph, and we make some progress toward proving this. We give equivalent conditions for cycle-maximal triangle-free graphs; show bounds on the numbers of cycles in graphs depending on numbers of vertices and edges, girth, and homomorphisms to small fixed graphs; and use the bounds to show that among regular graphs, the conjecture holds. We also consider graphs that are close to being regular, with the minimum and maximum degrees differing by at most a positive integer $k$ . For $k=1$ , we show that any such counterexamples have $n\le 91$ and are not homomorphic to $C_5$ ; and for any fixed $k$ there exists a finite upper bound on the number of vertices in a counterexample. Finally, we describe an algorithm for efficiently computing the matrix permanent (a #P-complete problem in general) in a special case used by our bounds.

preprint2013arXiv

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

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.

preprint2013arXiv

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

Let $P$ be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment $s\in P$ as its \emph{trajectory}. The camera can see a point $p\in P$ if there exists a point $q\in s$ such that $pq$ is a line segment normal to $s$ that is completely inside $P$ . In the \emph{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) while in the \emph{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 asked by Katz and Morgenstern (2011). We next show that the minimum-cardinality sliding cameras problem is \textsc{NP}-hard when $P$ is allowed to have holes, which partially answers another question asked by Katz and Morgenstern (2011).

preprint2013arXiv

Revisiting the Problem of Searching on a Line

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.

preprint2012arXiv

Robust Non-Parametric Data Approximation of Pointsets via Data Reduction

In this paper we present a novel non-parametric method of simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. We consider the problem of minimizing the average length of sequences of consecutive input points that lie on any one side of the simplified curve. Specifically, given a sequence $P$ of $n$ points in the plane that determine a simple polygonal chain consisting of $n-1$ segments, we describe algorithms for selecting an ordered subset $Q \subset P$ (including the first and last points of $P$ ) that determines a second polygonal chain to approximate $P$ , such that the number of crossings between the two polygonal chains is maximized, and the cardinality of $Q$ is minimized among all such maximizing subsets of $P$ . Our algorithms have respective running times $O(n^2\log n)$ when $P$ is monotonic and $O(n^2\log^2 n)$ when $P$ is an arbitrary simple polyline. Finally, we examine the application of our algorithms iteratively in a bootstrapping technique to define a smooth robust non-parametric approximation of the original sequence.

preprint2011arXiv

A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query

We revisit the range minimum query problem and present a new O(n)-space data structure that supports queries in O(1) time. 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 costs for query time or space.

preprint2011arXiv

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

The interference at a wireless node s can be modelled by the number of wireless nodes whose transmission ranges cover s. 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. We consider the model introduced by von Rickenback et al. (2005), in which each transmission range is represented by a ball and edges in the communication graph are symmetric. The problem is NP-complete in two dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. Furthermore, even in one dimension (the highway model), the problem's complexity is unknown and the maximum interference of a set of n wireless nodes can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we show how to solve the problem efficiently in settings typical for wireless ad hoc networks. In particular, we show that if node positions are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, for any fixed d, then the topology given by the closure of the Euclidean minimum spanning tree of P has maximum interference O(log n) with high probability. We extend this bound to a general class of communication graphs over a broad set of probability distributions. Next we present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on the expected maximum interference. Finally, we discuss an empirical evaluation of our algorithm with a suite of simulation results.

preprint2011arXiv

Linear-Space Data Structures for Range Mode Query in Arrays

A mode of a multiset $S$ is an element $a \in S$ of maximum multiplicity; that is, $a$ occurs at least as frequently as any other element in $S$ . Given a list $A[1:n]$ of $n$ items, we consider the problem of constructing a data structure that efficiently answers range mode queries on $A$ . Each query consists of an input pair of indices $(i, j)$ for which a mode of $A[i:j]$ must be returned. We present an $O(n^{2-2ε})$ -space static data structure that supports range mode queries in $O(n^ε)$ time in the worst case, for any fixed $ε\in [0,1/2]$ . When $ε= 1/2$ , this corresponds to the first linear-space data structure to guarantee $O(\sqrt{n})$ query time. We then describe three additional linear-space data structures that provide $O(k)$ , $O(m)$ , and $O(|j-i|)$ query time, respectively, where $k$ denotes the number of distinct elements in $A$ and $m$ denotes the frequency of the mode of $A$ . Finally, we examine generalizing our data structures to higher dimensions.

preprint2009arXiv

Improved Approximation Algorithms for Segment Minimization in Intensity Modulated Radiation Therapy

he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes in each row are consecutive. This has direct applications in intensity-modulated radiation therapy, an effective form of cancer treatment. We develop three approximation algorithms for matrices with arbitrarily many rows. Our first two algorithms improve the approximation factor from the previous best of $1+\log_2 h$ to (roughly) $3/2 \cdot (1+\log_3 h)$ and $11/6\cdot(1+\log_4{h})$ , respectively, where $h$ is the largest entry in the intensity matrix. We illustrate the limitations of the specific approach used to obtain these two algorithms by proving a lower bound of $\frac{(2b-2)}{b}\cdot\log_b{h} + \frac{1}{b}$ on the approximation guarantee. Our third algorithm improves the approximation factor from $2 \cdot (\log D+1)$ to $24/13 \cdot (\log D+1)$ , where $D$ is (roughly) the largest difference between consecutive elements of a row of the intensity matrix. Finally, experimentation with these algorithms shows that they perform well with respect to the optimum and outperform other approximation algorithms on 77% of the 122 test cases we consider, which include both real world and synthetic data.

preprint2000arXiv

The Rectilinear Crossing Number of K_10 is 62

A drawing of a graph G in the plane is said to be a rectilinear drawing of G if the edges are required to be line segments (as opposed to Jordan curves). We assume no three vertices are collinear. The rectilinear crossing number of G is the fewest number of edge crossings attainable over all rectilinear drawings of G. Thanks to Richard Guy, exact values of the rectilinear crossing number of K_n, the complete graph on n vertices, for n = 3,...,9, are known (Guy 1972, White and Beinke 1978, Finch 2000, Sloanes A014540). Since 1971, thanks to the work of David Singer (1971, Gardiner 1986), the rectilinear crossing number of K_10 has been known to be either 61 or 62, a deceptively innocent and tantalizing statement. The difficulty of determining the correct value is evidenced by the fact that Singer's result has withstood the test of time. In this paper we use a purely combinatorial argument to show that the rectilinear crossing number of K_10 is 62. Moreover, using this result, we improve an asymptotic lower bound for a related problem. Finally, we close with some new and old open questions that were provoked, in part, by the results of this paper, and by the tangled history of the problem itself.

preprint2000arXiv

Toward the Rectilinear Crossing Number of $K_n$ : New Drawings, Upper Bounds, and Asymptotics

Scheinerman and Wilf (1994) assert that `an important open problem in the study of graph embeddings is to determine the rectilinear crossing number of the complete graph K_n.' A rectilinear drawing of K_n is an arrangement of n vertices in the plane, every pair of which is connected by an edge that is a line segment. We assume that no three vertices are collinear, and that no three edges intersect in a point unless that point is an endpoint of all three. The rectilinear crossing number of K_n is the fewest number of edge crossings attainable over all rectilinear drawings of K_n. For each n we construct a rectilinear drawing of K_n that has the fewest number of edge crossings and the best asymptotics known to date. Moreover, we give some alternative infinite families of drawings of K_n with good asymptotics. Finally, we mention some old and new open problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stephane Durocher

Research overview

Is this your work?

14 publications

A structured latent space for human body motion generation

Minimum Ply Covering of Points with Unit Squares

Relating Graph Thickness to Planar Layers and Bend Complexity

Cycle-maximal triangle-free graphs

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

Revisiting the Problem of Searching on a Line

Robust Non-Parametric Data Approximation of Pointsets via Data Reduction

A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

Linear-Space Data Structures for Range Mode Query in Arrays

Improved Approximation Algorithms for Segment Minimization in Intensity Modulated Radiation Therapy

The Rectilinear Crossing Number of K_10 is 62

Toward the Rectilinear Crossing Number of $K_n$ : New Drawings, Upper Bounds, and Asymptotics

See the researcher in context

Building this map preview

Stephane Durocher

Research overview

Is this your work?

14 publications

A structured latent space for human body motion generation

Minimum Ply Covering of Points with Unit Squares

Relating Graph Thickness to Planar Layers and Bend Complexity

Cycle-maximal triangle-free graphs

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

Revisiting the Problem of Searching on a Line

Robust Non-Parametric Data Approximation of Pointsets via Data Reduction

A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

Linear-Space Data Structures for Range Mode Query in Arrays

Improved Approximation Algorithms for Segment Minimization in Intensity Modulated Radiation Therapy

The Rectilinear Crossing Number of K_10 is 62

Toward the Rectilinear Crossing Number of KnK_nKn​: New Drawings, Upper Bounds, and Asymptotics

See the researcher in context

Building this map preview

Toward the Rectilinear Crossing Number of $K_n$ : New Drawings, Upper Bounds, and Asymptotics