Source author record

Markus Wallinger

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics econ.TH Graphics Human-Computer Interaction Multiagent Systems

Catalog footprint

Research overview

4works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Finding a Battleship of Uncertain Shape

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in\{1,2\}$ . A ship is a subset of $\mathbb{Z}^d$ . Given a family $F$ of ships, we say that an infinite subset $X\subset\mathbb{Z}^d$ of the cells pierces $F$ , if it intersects each translate of each ship in $F$ (by a vector in $\mathbb{Z}^d$ ). In this work, we study the lowest possible (asymptotic) density $π(F)$ of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case $|F|=1$ (a single ship). As our main contribution, we present a formula for $π(F)$ when $F$ consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding $π(F)$ in 1D.

preprint2022arXiv

MosaicSets: Embedding Set Systems into Grid Graphs

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.

preprint2022arXiv

Multidimensional Manhattan Preferences

A preference profile with $m$ alternatives and $n$ voters is $d$ -Manhattan (resp. $d$ -Euclidean) if both the alternatives and the voters can be placed into the $d$ -dimensional space such that between each pair of alternatives, every voter prefers the one which has a shorter Manhattan (resp. Euclidean) distance to the voter. Following Bogomolnaia and Laslier [Journal of Mathematical Economics, 2007] and Chen and Grottke [Social Choice and Welfare, 2021] who look at $d$ -Euclidean preference profiles, we study which preference profiles are $d$ -Manhattan depending on the values $m$ and $n$ . First, we show that each preference profile with $m$ alternatives and $n$ voters is $d$ -Manhattan whenever $d$ $\geq$ min( $n$ , $m$ - $1$ ). Second, for $d = 2$ , we show that the smallest non $d$ -Manhattan preference profile has either three voters and six alternatives, or four voters and five alternatives, or five voters and four alternatives. This is more complex than the case with $d$ -Euclidean preferences (see [Bogomolnaia and Laslier, 2007] and [Bulteau and Chen, 2020].

preprint2021arXiv

On the Readability of Abstract Set Visualizations

Set systems are used to model data that naturally arises in many contexts: social networks have communities, musicians have genres, and patients have symptoms. Visualizations that accurately reflect the information in the underlying set system make it possible to identify the set elements, the sets themselves, and the relationships between the sets. In static contexts, such as print media or infographics, it is necessary to capture this information without the help of interactions. With this in mind, we consider three different systems for medium-sized set data, LineSets, EulerView, and MetroSets, and report the results of a controlled human-subjects experiment comparing their effectiveness. Specifically, we evaluate the performance, in terms of time and error, on tasks that cover the spectrum of static set-based tasks. We also collect and analyze qualitative data about the three different visualization systems. Our results include statistically significant differences, suggesting that MetroSets performs and scales better.

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.

Markus Wallinger

Research overview

Is this your work?

4 publications

Finding a Battleship of Uncertain Shape

MosaicSets: Embedding Set Systems into Grid Graphs

Multidimensional Manhattan Preferences

On the Readability of Abstract Set Visualizations

See the researcher in context

Building this map preview