Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
Bart M.P. Jansen and Jules J.H.M. Wulms.
Discrete Applied Mathematics,
2019.
－ Abstract
<p>
Garnero et al. (2015) recently introduced a framework based on dynamic programming to make applications of the protrusion replacement technique constructive and to obtain explicit upper bounds on the involved constants. They show that for several graph problems, for every boundary size t one can find an explicit set R
<sub>t</sub>
of representatives. Any subgraph H with a boundary of size t can be replaced with a representative H
<sup>′</sup>
∈R
<sub>t</sub>
such that the effect of this replacement on the optimum can be deduced from H and H
<sup>′</sup>
alone. Their upper bounds on the size of the graphs in R
<sub>t</sub>
grow triple-exponentially with t. In this paper we complement their results by lower bounds on the sizes of representatives, in terms of the boundary size t. For example, we show that each set of planar representatives R
<sub>t</sub>
for INDEPENDENT SET or DOMINATING SET contains a graph with Ω(2
<sup>t</sup>
∕4t) vertices. This lower bound even holds for sets that only represent the planar subgraphs of bounded pathwidth. To obtain our results we provide a lower bound on the number of equivalence classes of the canonical equivalence relation for INDEPENDENT SET on t-boundaried graphs. We also find an elegant characterization of the number of equivalence classes in general graphs, in terms of the number of monotone functions of a certain kind. Our results show that the number of equivalence classes is at most 2
<sup>
2
<sup>t</sup>
</sup>
, improving on earlier bounds of the form (t+1)
<sup>
2
<sup>t</sup>
</sup>
.
</p>
－ BibTeX
@article{lower-bounds-for-protrusion-replacement-by-counting-equivalence-classes:2019,
title = {Lower Bounds for Protrusion Replacement by Counting Equivalence Classes},
author = {Bart M.P. Jansen and Jules J.H.M. Wulms},
year = {2019},
bookTitle = {Discrete Applied Mathematics},
}
Spatially and Temporally Coherent Visual Summaries
Jules J.H.M. Wulms, Juri Buchmüller, Wouter Meulemans, Kevin A.B. Verbeek, and Bettina Speckmann.
arXiv,
2019.
－ Abstract
When exploring large time-varying data sets, visual summaries are a useful tool to identify time intervals of interest for further consideration. A typical approach is to represent the data elements at each time step in a compact one-dimensional form or via a one-dimensional ordering. Such 1D representations can then be placed in temporal order along a time line. There are two main criteria to assess the quality of the resulting visual summary: spatial quality -- how well does the 1D representation capture the structure of the data at each time step, and stability -- how coherent are the 1D representations over consecutive time steps or temporal ranges? We focus on techniques that create such visual summaries using 1D orderings for entities moving in 2D. We introduce stable techniques based on well-established dimensionality-reduction techniques: Principle Component Analysis, Sammon mapping, and t-SNE. Our Stable Principal Component method is explicitly parametrized for stability, allowing a trade-off between the two quality criteria. We conduct computational experiments that compare our stable methods to various state-of-the-art approaches using a set of well-established quality metrics that capture the two main criteria. These experiments demonstrate that our stable algorithms outperform existing methods on stability, without sacrificing spatial quality or efficiency.
－ BibTeX
@article{spatially-and-temporally-coherent-visual-summaries:2019,
title = {Spatially and Temporally Coherent Visual Summaries},
author = {Jules J.H.M. Wulms and Juri Buchmüller and Wouter Meulemans and Kevin A.B. Verbeek and Bettina Speckmann},
year = {2019},
bookTitle = {arXiv},
}
[ PDF ]
Stability Analysis of Kinetic Orientation-Based Shape Descriptors
Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
arXiv,
2019.
－ Abstract
We study three orientation-based shape descriptors on a set of continuously moving points P: the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor (sum of squared distances for principal component, area for oriented bounding box, and width for strip), and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. Alternatively, we can bound the speed with which the orientation of the descriptor may change. However, this can increase the cost (and hence lower the quality) of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. We first show that there is no stateless algorithm, which depends only on the input points in one time step and not on previous states, that both approximates the minimum cost of a shape descriptor and achieves bounded speed. On the other hand, if we can use the previous state of the shape descriptor to compute the new state, then we can define "chasing" algorithms that attempt to follow the optimal orientation with bounded speed. Under mild conditions, we show that chasing algorithms with sufficient bounded speed approximate the optimal cost at every time step for oriented bounding boxes and strips, but not for principal components. The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used to perform this analysis are of independent interest.
－ BibTeX
@article{stability-analysis-of-kinetic-orientation-based-shape-descriptors:2019,
title = {Stability Analysis of Kinetic Orientation-Based Shape Descriptors},
author = {Wouter Meulemans and Kevin Verbeek and Jules Wulms},
year = {2019},
bookTitle = {arXiv},
}
[ PDF ]