检索结果-内蒙古大学图书馆

Transitions in Dynamic Point Labeling

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Vienna Austria Algorithm Engineering Group TU Dortmund Dortmund Germany

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. Copyright © 2022, The Authors. All rights reserved.

关键词：

Exploring semi-automatic map labeling

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Klute, Fabian Li, Guangping Löffler, Raphael Nöllenburg, Martin Schmidt, Manuela Algorithms and Complexity Group TU Wien Vienna Austria Research Group Cartography TU Wien Vienna Austria

Label placement in maps is a very challenging task that is critical for the overall map quality. Most previous work focused on designing and implementing fully automatic solutions, but the resulting visual and aesthetic quality has not reached the same level of sophistication that skilled human cartographers achieve. We investigate a different strategy that combines the strengths of humans and algorithms. In our proposed method, first an initial labeling is computed that has many well-placed labels but is not claiming to be perfect. Instead it serves as a starting point for an expert user who can then interactively and locally modify the labeling where necessary. In an iterative human-in-the-loop process alternating between user modifications and local algorithmic updates and refinements the labeling can be tuned to the user's needs. We demonstrate our approach by performing different possible modification steps in a sample workflow with a prototypical interactive labeling editor. Further, we report computational performance results from a simulation experiment in QGIS, which investigates the differences between exact and heuristic algorithms for semi-automatic map labeling. To that end, we compare several alternatives for recomputing the labeling after local modifications and updates, as a major ingredient for an interactive labeling editor. Copyright © 2019, The Authors. All rights reserved.

关键词： Heuristic algorithms

Parameterized complexity of feature selection for categorical data clustering

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m − relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k, B, |Σ|) · mg(k,|Σ|) · n2 for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental pro

关键词： Clustering algorithms

Boundary Labeling in a Circular Orbit

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © 2024, CC BY.

关键词： Polynomial approximation

Geometric systems of unbiased representatives 31

学校读者我要写书评

暂无评论

Geometric systems of unbiased representatives

31st Canadian Conference on Computational Geometry, CCCG 2019

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo National Institute of Science Education and Research School of Computer Sciences HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université France

Let P be a set of points in Rd, B a bicoloring of P and O a family of geometric objects (that is, intervals, boxes, balls, etc). An object from O is called balanced with respect to B if it contains the same number of points from each color of B. For a collection B of bicolorings of P, a geometric system of unbiased representatives (GSUR) is a subset such that for any bicoloring B of β there is an object in O0 that is balanced with respect to B. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives. © CCCG 2019. All rights reserved.

关键词： Computational geometry

Parameterized algorithms for Queue Layouts

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2022年第3期26卷 335-352页

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Bruxelles Belgium Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h sets, called queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. © 2022, Brown University. All rights reserved.

关键词： Parameter estimation

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth 31

学校读者我要写书评

暂无评论

Space-Efficient Parameterized Algorithms on Graphs of Low Sh...

31st Annual European Symposium on algorithms, ESA 2023

作者： Bergougnoux, Benjamin Chekan, Vera Ganian, Robert Kanté, Mamadou Moustapha Mnich, Matthias Oum, Sang-Il Pilipczuk, Michal van Leeuwen, Erik Jan Institute of Informatics University of Warsaw Poland Humboldt-Universität zu Berlin Germany Algorithms and Complexity Group TU Wien Austria Université Clermont Auvergne Clermont Auvergne INP LIMOS CNRS Clermont-Ferrand France Hamburg University of Technology Institute for Algorithms and Complexity Germany Daejeon Korea Republic of Department of Mathematical Sciences KAIST Daejeon Korea Republic of Dept. Information and Computing Sciences Utrecht University Netherlands

ISBN: (纸本)9783959772952

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, Independent Set can be solved in time 2O(dk) · nO(1) using O(dk2 log n) space;Max Cut can be solved in time nO(dk) using O(dk log n) space;and Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial. © Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthia

关键词： Dynamic programming

On Families of Planar DAGs with Constant Stack Number

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Nöllenburg, Martin Pupyrev, Sergey Algorithms and Complexity Group TU Wien Austria Meta Menlo ParkCA United States

A k-stack layout (or k-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing edges with respect to the vertex order. The stack number of a graph is the minimum k such that it admits a k-stack layout. In this paper we study a long-standing problem regarding the stack number of planar directed acyclic graphs (DAGs), for which the vertex order has to respect the orientation of the edges. We investigate upper and lower bounds on the stack number of several families of planar graphs: We improve the constant upper bounds on the stack number of single-source and monotone outerplanar DAGs and of outerpath DAGs, and improve the constant upper bound for upward planar 3-trees. Further, we provide computer-aided lower bounds for upward (outer-) planar DAGs. Copyright © 2021, The Authors. All rights reserved.

关键词： Directed graphs

How to find a good explanation for clustering?

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Lochet, William Purohit, Nidhi Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria

k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost [ICML 2020] proposed an elegant model of explainable k-means and k-median clustering. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the "best explanation" by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering. © 2021, CC BY.

关键词： Decision trees