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

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 129卷

作者： Depian, Thomas Noellenburg, Martin Terziadis, Soeren Wallinger, Markus TU Wien Algorithms & Complex Grp Vienna Austria TU Eindhoven Algorithms Cluster Eindhoven Netherlands Tech Univ Munich Chair Efficient Algorithms Munich Germany

Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomialtime algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Boundary labeling Grouping constraints Ordering constraints Dynamic programming Computational complexity

来源：评论

学校读者我要写书评

暂无评论

GdMetriX - A NetworkX Extension For Graph Drawing Metrics 32

GdMetriX - A NetworkX Extension For Graph Drawing Metrics

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Nöllenburg, Martin Röder, Sebastian Wallinger, Markus Algorithms and Complexity Group TU Wien Austria TU Wien Austria Chair for Efficient Algorithms Technical University of Munich Germany

ISBN: (纸本)9783959773430

networkX is a well-established Python library for network analysis. With gdMetriX, we aim to extend the functionality of networkX and provide common quality metrics used in the field of graph drawing, such as the number of crossings or the angular resolution. In addition, the package provides easy-to-use access to the graph datasets provided by the 'Graph Layout Benchmark Datasets' project from the Northeastern University Visualization Lab. © Martin Nöllenburg, Sebastian Röder, and Markus Wallinger.

关键词： Data visualization

来源：评论

学校读者我要写书评

暂无评论

Boundary Labeling in a Circular Orbit 32

Boundary Labeling in a Circular Orbit

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 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 Chair for Efficient Algorithms TU Munich Germany

ISBN: (纸本)9783959773430

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. © Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

How Do People Perceive Bundling? An Experiment 25

How Do People Perceive Bundling? An Experiment

引用

2025 CHI Conference on Human Factors in Computing Systems, CHI 2025

作者： Wallinger, Markus Akbulut, Osman Rufai, Kabir Ahmed Purchase, Helen C. Archambault, Daniel Chair for Efficient Algorithms Technical University of Munich Munich Germany Department of Computer Engineering Faculty of Engineering Duzce University Duzce Turkey Faculty of Information Technology Monash University Melborne VIC Australia Newcastle University Newcastle United Kingdom

ISBN: (纸本)9798400713941

We present an exploratory study on how people perceive visualizations of spatial social networks generated by edge bundling algorithms. Although these algorithms successfully minimize clutter in node-link diagrams, they do so through various methods that can sometimes create false connections between nodes. We conducted a qualitative experiment involving participants with technical expertise but no prior knowledge of edge bundling algorithms. Participants described their perceptions of both bundled and straight-line visualizations in open-ended tasks. Analysis of their annotations and transcripts revealed a general preference for bundled visualizations. However, when it came to false connections, participants tended to follow them in tightly bundled diagrams while also vocalizing that these drawings were more ambiguous. The routing of bundles influenced the perception of clusters and participants assigned more or fewer nodes to the clusters, depending on the routing of bundles. Participants' unfamiliarity with the dataset led them to use analogies to describe the bundled drawings, potentially adding perceived semantic meaning to the data. © 2025 Copyright held by the owner/author(s).

关键词： Edge Bundling Empirical Study Network Visualization Qualitative Experiment

来源：评论

学校读者我要写书评

暂无评论

Memories on Vladimir Gerdt

引用

JOURNAL OF SYMBOLIC COMPUTATION 2022年 109卷 50-56页

作者： Mayr, Ernst W. Seiler, Werner M. V. Vorozhtsov, Evgenii Tech Univ Munich Dept Informat Chair Efficient Algorithms I14Boltzmannstr 3 D-85748 Garching Germany Univ Kassel Inst Math D-34109 Kassel Germany Russian Acad Sci Siberian Branch Khristianovich Inst Theoret & Appl Mech Novosibirsk 630090 Russia

来源：评论

学校读者我要写书评

暂无评论

Refining Tournament Solutions via Margin of Victory 34

Refining Tournament Solutions via Margin of Victory

引用

34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence

作者： Brill, Markus Schmidt-Kraepelin, Ulrike Suksompong, Warut Tech Univ Berlin Chair Efficient Algorithms Berlin Germany Univ Oxford Dept Comp Sci Oxford England

ISBN: (纸本)9781577358350

Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation.

关键词： Refining

来源：评论

学校读者我要写书评

暂无评论

Approval-Based Apportionment 34

Approval-Based Apportionment

引用

34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence

作者： Brill, Markus Goelz, Paul Peters, Dominik Schmidt-Kraepelin, Ulrike Wilkerl, Kai Tech Univ Berlin Chair Efficient Algorithms Berlin Germany Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA

ISBN: (纸本)9781577358350

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Random Projections and Sampling algorithms for Clustering of High-Dimensional Polygonal Curves 33

Random Projections and Sampling Algorithms for Clustering of...

引用

33rd Conference on Neural Information Processing Systems (NeurIPS)

作者： Meintrup, Stefan Munteanu, Alexander Rohde, Dennis TU Dortmund Univ Fac Comp Sci Dortmund Germany TU Dortmund Univ Dortmund Data Sci Ctr Dortmund Germany TU Dortmund Univ Chair Efficient Algorithms & Complex Theory Dortmund Germany

We study the k-median clustering problem for high-dimensional polygonal curves with finite but unbounded number of vertices. We tackle the computational issue that arises from the high number of dimensions by defining a Johnson-Lindenstrauss projection for polygonal curves. We analyze the resulting error in terms of the Frechet distance, which is a tractable and natural dissimilarity measure for curves. Our clustering algorithms achieve sublinear dependency on the number of input curves via subsampling. Also, we show that the Frechet distance can not be approximated within any factor of less than root 2 by probabilistically reducing the dependency on the number of vertices of the curves. As a consequence we provide a fast, CUDA-parallelized version of the Alt and Godau algorithm for computing the Frechet distance and use it to evaluate our results empirically.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Random projections and sampling algorithms for clustering of high-dimensional polygonal curves

arXiv

引用

arXiv 2019年

作者： Meintrup, Stefan Munteanu, Alexander Rohde, Dennis Faculty of Computer Science TU Dortmund University Dortmund Germany Dortmund Data Science Center TU Dortmund University Dortmund Germany Chair of Efficient Algorithms and Complexity Theory TU Dortmund University Dortmund Germany

We study the center and median clustering problems for high-dimensional polygonal curves with finite but unbounded complexity. We tackle the computational issue that arises from the high number of dimensions by defining a Johnson-Lindenstrauss projection for polygonal curves. We analyze the resulting error in terms of the Fréchet distance, which is a natural dissimilarity measure for curves. Our algorithms for the median clustering achieve sublinear dependency on the number of input curves via subsampling. For the center clustering we utilize Buchin et al. (2019a) algorithm that achieves linear running-time in the number of input curves. We evaluate our results empirically utilizing a fast, CUDA-parallelized variant of the Alt and Godau algorithm for the Fréchet distance. Our experiments show that our clustering algorithms have fast and accurate practical implementations that yield meaningful results on real world data from various physical domains. Copyright © 2019, The Authors. All rights reserved.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Numerical optimisation of the pseudopotential-based lattice Boltzmann method

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2016年第Part2期17卷 384-393页

作者： Kuellmer, Knut Kraemer, Andreas Reith, Dirk Joppich, Wolfgang Foysi, Holger Bonn Rhein Sieg Univ Appl Sci Inst Technol Renewables & Energy Efficient Engn Grantham Allee 20 D-53757 St Augustin Germany Fraunhofer Inst Algorithms & Sci Comp Dept Simulat Engn D-53757 St Augustin Germany Univ Siegen Chair Fluid Mech Paul Bonatz Str 9-11 D-57068 Siegen Germany

Pseudopotential-based lattice Boltzmann models provide an efficient means to simulate multiphase flows. Although thoroughly analysed and extended, they still suffer from various numerical deficiencies, such as stability issues at large density and viscosity ratios as well as spurious velocities in interfacial regions. In this work, we show how to optimise the model-numerically with regard to the latter. This optimised scheme is analysed in static as well as oscillating droplet simulations and is compared to different higher order isotropic schemes. We found that the optimised scheme substantially lowers spurious velocities and competes well with comparable schemes in both test cases. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Spurious velocity Multiphase flow Numerical optimisation Lattice Boltzmann Shan-Chen model

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：