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.

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.

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 spatiotemporal features of human motion. Code is available at https://github.com/mmarsot/A_structured_latent_space.

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 $\Gamma$ of $G$, where each vertex is mapped to a point and each edge is mapped to a polygonal chain between the corresponding endpoints. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of $\Gamma$ is the maximum number of bends per edge in $\Gamma$, and the layer complexity of $\Gamma$ is the minimum integer $r$ such that the set of polygonal chains in $\Gamma$ 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$ planar layers with bend complexity 2 (resp., $3n+O(1)$). 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$ planar layers with $2.25n+O(1)$ bends per edge. We then develop another technique to draw thickness-$t$ graphs on $t$ planar layers with bend complexity $O(\sqrt{2}^{t} \cdot n^{1-(1/\beta)})$, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. If $t$ is fixed, then this gives a sublinear bound on the bend complexity. Previously, the bend complexity was not known to be sublinear for any $t>2$. Finally, we show that graphs with linear arboricity $k$ can be drawn on $k$ planar layers with bend complexity $\frac{3(k-1)n}{(4k-2)}$. Note that we do not compute the edge-partition of the given graph into $t$ planar subgraphs or into $k$ linear forests, but we assume that such a partition is given as an input to our algorithm.

Test case selection is a classic testing technique to choose a subset of existing test cases for execution, due to the limited budget and tight deadlines. While `code coverage' is the state of practice among test case selection heuristics, recent literature has shown that `test case diversity' is also a very promising approach. In this paper, we first compare these two heuristics for test case selection in several real-world case studies (Apache Ant, Derby, JBoss, NanoXML and Math). The results show that neither of the two techniques completely dominates the other, but they can potentially be complementary. Therefore, we next propose a novel approach that maximizes both code coverage and diversity among the selected test cases using NSGA-II multi- objective optimization, and the results show a significant improvement in fault detection rate. Specifically, sometimes this novel approach detects up to 16\%(Ant), 10\%(JBoss), and 14\% (Math) more faults compared to either of coverage or diversity-based approaches, when the testing budget is less than 20\% of the entire test suite execution cost.

We give an $O(n\log ^3 n)$-time linear-space algorithm that, given a plane 3-tree $G$ with $n$ vertices and a set $S$ of $n$ points in the plane, determines whether $G$ has a point-set embedding on $S$ (i.e., a planar straight-line drawing of $G$ where each vertex is mapped to a distinct point of $S$), improving the $O(n^{4/3+\varepsilon})$-time $O(n^{4/3})$-space algorithm of Moosa and Rahman [Lecture Notes in Comput. Sci. 6842, Springer, New York, 2011, pp. 204--212]. Given an arbitrary plane graph $G$ and a point set $S$, Kaufmann and Wiese [J. Graph Algorithms Appl., 6 (2002), pp. 115--129] gave an algorithm to compute 2-bend point-set embeddings of $G$ on $S$. Later, Di Giacomo and Liotta [Lecture Notes in Comput. Sci. 5942, Springer, New York, 2010, pp. 35--46] showed how such a drawing can be computed using $O(W^3)$ area, where $W$ is the length of the longest edge of the bounding box of $S$. Their algorithm uses $O(W^3)$ area even when the input graphs are restricted to plane 3-trees. We introduce new techniques for computing $2$-bend point-set embeddings of plane 3-trees that take only $O(W^2)$ area. We also give approximation algorithms for point-set embeddings of plane $3$-trees. Our results on 2-bend point-set embeddings and approximate point-set embeddings hold for partial plane $3$-trees (e.g., series-parallel graphs and Halin graphs).

Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (i.e., a power level) to each node such that the resulting communication graph is connected while minimizing the maximum (respectively, average) interference. We consider the model introduced by von Rickenbach (2005), in which each wireless node is represented by a point in Euclidean space on which is centered a transmission range represented by a ball, and edges in the corresponding graph are symmetric. The problem is NP-complete in two or more dimensions (Buchin 2008), and no polynomial-time approximation algorithm is known. We show how to solve the problem efficiently in settings typical for wireless ad hoc networks. If nodes are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, then the topology given by the closure of the Euclidean minimum spanning tree of P has O(log n) maximum interference with high probability and O(1) expected interference. We extend the first bound to a general class of communication graphs over a broad set of probability distributions. We present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on expected maximum interference. Finally, we disprove a conjecture of Devroye and Morin (2012) relating the maximum interference of the Euclidean minimum spanning tree to the optimal maximum interference attainable.

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 an array A[1:n] of n elements, we consider a basic problem: constructing a static 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. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n) loglog n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n / log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) by sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n^(1-1/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(1-1/d^2)) time).

We examine bounds on the locality of routing. A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know a) the subgraph corresponding to all network nodes within k hops of itself, for some value of k, b) the node from which the message originated, and c) which of its neighbours last forwarded the message. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies on a network modelled by a connected undirected graph. In particular, we establish tight bounds on k for the feasibility of deterministic k-local routing for various combinations of these parameters, as well as corresponding bounds on dilation (the worst-case ratio of actual route length to shortest path length).