|
A. Bonerath, B. Niedermann, J. Diederich, Y. Orgeig, J. Oehrlein, and J.-H. Haunert. A time-windowed data structure for spatial density maps. In Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20), pages 15-24. 2020.
abstract
doi
bibtex
|
| The visualization of spatio-temporal data helps researchers
understand global processes such as animal migration. In particular,
interactively restricting the data to different time windows reveals
new insights into the short-term and long-term changes of the
research data. Inspired by this use case, we consider the
visualization of point data annotated with time stamps. We pick up
classical, grid-based density maps as the underlying visualization
technique and enhance them with an efficient data structure for
arbitrarily specified time-window queries. The running time of the
queries is logarithmic in the total number of points and linear in
the number of actually colored cells. In experiments on real-world
data we show that the data structure answers time-window queries
within milliseconds, which supports the interactive exploration of large
point sets. Further, the data structure can be used to visualize
additional decision problems, e.g., it can answer whether
the sum or maximum of additional weights given with the points
exceed a certain threshold. We have defined the data structure
general enough to also support multiple thresholds expressed by
different colors. @inproceedings{bhn-twdssdm-20,
abstract = {The visualization of spatio-temporal data helps researchers
understand global processes such as animal migration. In particular,
interactively restricting the data to different time windows reveals
new insights into the short-term and long-term changes of the
research data. Inspired by this use case, we consider the
visualization of point data annotated with time stamps. We pick up
classical, grid-based density maps as the underlying visualization
technique and enhance them with an efficient data structure for
arbitrarily specified time-window queries. The running time of the
queries is logarithmic in the total number of points and linear in
the number of actually colored cells. In experiments on real-world
data we show that the data structure answers time-window queries
within milliseconds, which supports the interactive exploration of large
point sets. Further, the data structure can be used to visualize
additional decision problems, e.g., it can answer whether
the sum or maximum of additional weights given with the points
exceed a certain threshold. We have defined the data structure
general enough to also support multiple thresholds expressed by
different colors.},
author = {Bonerath, A. and Niedermann, B. and Diederich, J. and Orgeig, Y. and Oehrlein, J. and Haunert, J.-H.},
booktitle = {Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20)},
doi = {10.1145/3397536.3422242},
pages = {15--24},
title = {{A Time-Windowed Data Structure for Spatial Density Maps}},
year = {2020}
}
|
|
B. Niedermann, and I. Rutter. An integer-linear program for bend-minimization in ortho-radial drawings. In David Auber, and Pavel Valtr, editors, Lecture Notes in Computer Science. Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20). Springer, 2020.
abstract
bibtex
|
| An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds. @inproceedings{nr-ilpbmord2020,
abstract = {An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.},
author = {B. Niedermann and I. Rutter},
booktitle = {Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20)},
editor = {Auber, David and Valtr, Pavel},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings}},
year = {2020}
}
|
|
Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li, and Martin Nöllenburg. Balanced independent and dominating sets on colored interval graphs. In Proc. 36th European Workshop on Computational Geometry (EuroCG 2020), pages 66:1-66:6. 2020.
abstract
bibtex
|
| We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely \emph$f$-Balanced Independent Set ($f$-BIS) and \emph$f$-Balanced Dominating Set ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a $k$-coloring $γo̧lon V i̊ghtarrow \1,\ldots,k\$ for some $k ∈\mathbb N$. A subset of vertices $S⊆V$ is called \emph$f$-balanced if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are \NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two \FPT\ algorithms, one parameterized by $(f,k)$ and the other by the vertex cover number of $G$. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs. @inproceedings{BhoreEtAl2020,
abstract = {We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely \emph{$f$-Balanced Independent Set} ($f$-BIS) and \emph{$f$-Balanced Dominating Set} ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a $k$-coloring $\gamma \colon V \rightarrow \{1,\ldots,k\}$ for some $k \in \mathbb N$. A subset of vertices $S\subseteq V$ is called \emph{$f$-balanced} if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are \NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two \FPT\ algorithms, one parameterized by $(f,k)$ and the other by the vertex cover number of $G$. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs.},
author = {Sujoy Bhore and Jan{-}Henrik Haunert and Fabian Klute and Guangping Li and Martin N{\"{o}}llenburg},
booktitle = {Proc. 36th European Workshop on Computational Geometry (EuroCG 2020)},
pages = {66:1--66:6},
title = {Balanced Independent and Dominating Sets on Colored Interval Graphs},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_66.pdf},
year = {2020}
}
|
|
Dongliang Peng, Alexander Wollf, and Jan-Henrik Haunert. Finding optimal sequences for area aggregation: A* vs. integer linear programming. ACM Transactions on Spatial Algorithms and Systems, 7(1):4:1-4:40, 2020.
abstract
doi
bibtex
|
| To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons each of
which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the A$^*$ algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that A$^*$ finds optimal aggregation sequences for more instances than the other two methods within a given time frame. @article{Peng2020,
abstract = {To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons each of
which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the A$^*$ algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that A$^*$ finds optimal aggregation sequences for more instances than the other two methods within a given time frame.},
author = {Dongliang Peng and Alexander Wollf and Jan{-}Henrik Haunert},
doi = {10.1145/3409290},
journal = {{ACM} Transactions on Spatial Algorithms and Systems},
number = {1},
pages = {4:1--4:40},
title = {Finding Optimal Sequences for Area Aggregation: {A}* vs. Integer Linear Programming},
volume = {7},
year = {2020}
}
|
|
Matan Mor, Johannes Oehrlein, Jan-Henrik Haunert, and Sagi Dalyot. Whom to follow? A comparison of walking routes computed based on social media photos from different types of contributors. In volume 1. Proc. 23rd AGILE Conference on Geographic Information Science (AGILE 2020), pages 16. 2020.
abstract
doi
bibtex
|
| Since many tourists share the photos they take on social media channels, large collections of tourist attraction photos are easily accessible online. Recent research has dealt with identifying popular places from these photos, as well as computing city tourism routes based on these photo collections. Although current approaches show great potential, many tourism attractions suffer from being overrun by tourists, not least because many tourists are aware of only a few tourism hot spots that are trending. In the worst case, automatic city route recommendations based on social media photos will intensify this issue and disappoint tourists who seek individual experiences. In the best case, however, if individual preferences are appropriately incorporated into the route planning algorithm, more personalized route recommendations will be achieved. In this paper, we suggest distinguishing two different types of photo contributors, namely: first-time visitors who are usually tourists who "follow the crowd" (e.g., to visit the top tourist attractions), and repeated visitors who are usually locals who "don’t follow the crowd" (e.g., to visit photogenic yet less well-known places). This categorization allows the user to decide how to trade the one objective off against the other. We present a novel method based on a classification of photographers into locals and tourists, and show how to incorporate this information into an algorithmic routing framework based on the Orienteering Problem approach. In detailed experiments we analyze how choosing the parameter that models the trade-off between both objectives influences the optimal route found by the algorithm, designed to serve the user’s travel objective and preferences in terms of visited attraction types. @inproceedings{Mor2020,
abstract = {Since many tourists share the photos they take on social media channels, large collections of tourist attraction photos are easily accessible online. Recent research has dealt with identifying popular places from these photos, as well as computing city tourism routes based on these photo collections. Although current approaches show great potential, many tourism attractions suffer from being overrun by tourists, not least because many tourists are aware of only a few tourism hot spots that are trending. In the worst case, automatic city route recommendations based on social media photos will intensify this issue and disappoint tourists who seek individual experiences. In the best case, however, if individual preferences are appropriately incorporated into the route planning algorithm, more personalized route recommendations will be achieved. In this paper, we suggest distinguishing two different types of photo contributors, namely: first-time visitors who are usually tourists who "follow the crowd" (e.g., to visit the top tourist attractions), and repeated visitors who are usually locals who "don’t follow the crowd" (e.g., to visit photogenic yet less well-known places). This categorization allows the user to decide how to trade the one objective off against the other. We present a novel method based on a classification of photographers into locals and tourists, and show how to incorporate this information into an algorithmic routing framework based on the Orienteering Problem approach. In detailed experiments we analyze how choosing the parameter that models the trade-off between both objectives influences the optimal route found by the algorithm, designed to serve the user’s travel objective and preferences in terms of visited attraction types.},
author = {Matan Mor and Johannes Oehrlein and Jan-Henrik Haunert and Sagi Dalyot},
booktitle = {Proc. 23rd {AGILE} Conference on Geographic Information Science (AGILE 2020)},
doi = {10.5194/agile-giss-1-16-2020},
pages = {16},
title = {Whom to Follow? {A} Comparison of Walking Routes Computed Based on Social Media Photos from Different Types of Contributors},
volume = {1},
year = {2020}
}
|
|
Hansjörg Kutterer, Hans Neuner, Helmut Mayer, Jan-Henrik Haunert, and Alexandra Weitkamp. Forschungsvorhaben. In Klaus Kummer, Theo Kötter, Hansjörg Kutterer, and Stefan Ostrau, editors. Das deutsche Vermessungs- und Geoinformationswesen 2020, pages 1067-1102. Wichmann Verlag, Heidelberg, Germany, 2020.
bibtex
|
| @incollection{Kutterer2020,
author = {Hansj\"{o}rg Kutterer and Hans Neuner and Helmut Mayer and Jan-Henrik Haunert and Alexandra Weitkamp},
booktitle = {Das deutsche Vermessungs- und Geoinformationswesen 2020},
chapter = {19},
editor = {Klaus Kummer and Theo K\"{o}tter and Hansj\"{o}rg Kutterer and Stefan Ostrau},
isbn = {978-3-87907-676-5},
pages = {1067--1102},
publisher = {Wichmann Verlag, Heidelberg, Germany},
title = {Forschungsvorhaben},
year = {2020}
}
|
|
H.-Y. Wu, B. Niedermann, S. Takahashi, M. J. Roberts, and M. Nöllenburg. A survey on transit map layout - from design, machine, and human perspectives. Computer Graphics Forum, 39(3), 2020.
abstract
doi
bibtex
|
| Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions. @article{wntrn-stlfdmhp-20,
abstract = {Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions.},
author = {Wu, H.-Y. and Niedermann, B. and Takahashi, S. and Roberts, M. J. and Nöllenburg, M.},
doi = {10.1111/cgf.14030},
journal = {Computer Graphics Forum},
number = {3},
title = {A Survey on Transit Map Layout -- from Design, Machine, and Human Perspectives},
url = {https://diglib.eg.org/bitstream/handle/10.1111/cgf14030/v39i3pp619-646.pdf},
volume = {39},
year = {2020}
}
|
|
Y. Dehbi, L. Klingbeil, and L. Plümer. Uav mission planning for automatic exploration and semantic mapping. ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLIII-B1-2020:521-526, 2020.
abstract
doi
bibtex
|
| Unmanned Aerial Vehicles (UAVs) are used for the inspection of areas which are otherwise difficult to access. Autonomous monitoring and navigation requires a background knowledge on the surroundings of the vehicle. Most mission planing systems assume collision-
free pre-defined paths and do not tolerate a GPS signal outage. Our approach makes weaker assumptions. This paper introduces a mission planing platform allowing for the integration of environmental prior knowledge such as 3D building and terrain models. This
prior knowledge is integrated to pre-compute an octomap for collision detection. The semantically rich building models are used to specify semantic user queries such as roof or facade inspection. A reasoning process paves the way for semantic mission planing of
hidden and a-priori unknown objects. Subsequent scene interpretation is performed by an incremental parsing process. @article{dehbi2020mission,
abstract = {Unmanned Aerial Vehicles (UAVs) are used for the inspection of areas which are otherwise difficult to access. Autonomous monitoring and navigation requires a background knowledge on the surroundings of the vehicle. Most mission planing systems assume collision-
free pre-defined paths and do not tolerate a GPS signal outage. Our approach makes weaker assumptions. This paper introduces a mission planing platform allowing for the integration of environmental prior knowledge such as 3D building and terrain models. This
prior knowledge is integrated to pre-compute an octomap for collision detection. The semantically rich building models are used to specify semantic user queries such as roof or facade inspection. A reasoning process paves the way for semantic mission planing of
hidden and a-priori unknown objects. Subsequent scene interpretation is performed by an incremental parsing process.},
author = {Dehbi, Y. and Klingbeil, L. and Pl\"umer, L.},
doi = {10.5194/isprs-archives-XLIII-B1-2020-521-2020},
journal = {ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences},
pages = {521--526},
series = {ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences (ISPRS Congress, Nice)},
title = {UAV mission planning for automatic exploration and semantic mapping},
volume = {XLIII-B1-2020},
year = {2020}
}
|
|
A. Gemsa, B. Niedermann, and M. Nöllenburg. A unified model and algorithms for temporal map labeling. Algorithmica, 82:2702-2736, 2020.
abstract
doi
bibtex
|
| We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels’ presences, activities and conflicts. One of the model’s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W[1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms. @article{gnn-umatml20,
abstract = {We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels’ presences, activities and conflicts. One of the model’s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W[1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.},
author = {Gemsa, A. and Niedermann, B. and Nöllenburg, M.},
doi = {10.1007/s00453-020-00694-7},
journal = {Algorithmica},
pages = {2702--2736},
title = {A Unified Model and Algorithms for Temporal Map Labeling},
volume = {82},
year = {2020}
}
|
|
A. Bonerath, J.-H. Haunert, and B. Niedermann. Tight rectilinear hulls of simple polygons. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20). 2020. trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U
abstract
bibtex
|
| A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C.
The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints.
We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap
with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances
the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields
such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls. @inproceedings{bhn-trhsp-20,
abstract = {A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C.
The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints.
We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap
with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances
the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields
such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.},
author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)},
note = {trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U},
title = {{Tight Rectilinear Hulls of Simple Polygons}},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/eurocg20_proceedings.pdf},
year = {2020}
}
|
|
A. Bonerath, J.-H. Haunert, and B. Niedermann. Dynamic aggregation of geo-objects for the interactive exploration of research data. In volume 29. Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany, pages 488-496. 2020.
abstract
bibtex
|
| In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research. @inproceedings{bhn-dagoierd20,
abstract = {In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.},
author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
booktitle = {Publikationen der Deutschen Gesellschaft f\"ur Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany},
number = {0},
pages = {488--496},
title = {Dynamic Aggregation of Geo-Objects for the Interactive Exploration of Research Data},
volume = {29},
year = {2020}
}
|
|
A. Gemsa, B. Niedermann, and M. Nöllenburg. Placing labels in road maps: algorithms and complexity. Algorithmica, 0(0):1-28, 2020. Online first.
abstract
doi
bibtex
|
| A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in cubic running time if the road map is an embedded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps. @article{gnn-plrmac20,
abstract = {A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in cubic running time if the road map is an embedded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.},
author = {Gemsa, A. and Niedermann, B. and Nöllenburg, M.},
doi = {10.1007/s00453-020-00678-7},
journal = {Algorithmica},
note = {Online first.},
number = {0},
pages = {1--28},
title = {Placing Labels in Road Maps: Algorithms and Complexity},
volume = {0},
year = {2020}
}
|
|
A. Corbin, B. Niedermann, A. Nothnagel, Haas R., and J.-H. Haunert. Combinatorial optimization applied to VLBI scheduling. Journal of Geodesy, 94(19):1-22, 2020.
abstract
doi
bibtex
|
| Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes. @article{cnnhh-coas20,
abstract = {Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes.},
author = {Corbin, A. and Niedermann, B. and Nothnagel, A. and Haas R. and Haunert, J.-H.},
doi = {10.1007/s00190-020-01348-w},
journal = {Journal of Geodesy},
number = {19},
pages = {1--22},
title = {Combinatorial optimization applied to {VLBI} scheduling},
volume = {94},
year = {2020}
}
|
|
Jutta A. Baldauf, Lucia Vedder, Heiko Schoof, and Frank Hochholdinger. Robust non-syntenic gene expression patterns in diverse maize hybrids during root development. Journal of Experimental Botany, 71(3):865-876, 2020.
abstract
doi
bibtex
|
| Distantly related maize (Zea mays, L.) inbred lines exhibit an exceptional degree of structural genomic diversity, which is probably unique among plants. This study systematically investigated the developmental and genotype-dependent regulation of the primary root transcriptomes of a genetically diverse panel of maize F1-hybrids and their parental inbred lines. While we observed substantial transcriptomic changes during primary root development, we demonstrated that hybrid-associated gene expression patterns, including differential, non-additive, and allele-specific transcriptome profiles, are particularly robust to these developmental fluctuations. @article{Vedder2020a,
abstract = {Distantly related maize (Zea mays, L.) inbred lines exhibit an exceptional degree of structural genomic diversity, which is probably unique among plants. This study systematically investigated the developmental and genotype-dependent regulation of the primary root transcriptomes of a genetically diverse panel of maize F1-hybrids and their parental inbred lines. While we observed substantial transcriptomic changes during primary root development, we demonstrated that hybrid-associated gene expression patterns, including differential, non-additive, and allele-specific transcriptome profiles, are particularly robust to these developmental fluctuations.},
author = {Baldauf, Jutta A. and Vedder, Lucia and Schoof, Heiko and Hochholdinger, Frank},
doi = {10.1093/jxb/erz452},
journal = {Journal of Experimental Botany},
number = {3},
pages = {865--876},
title = {Robust non-syntenic gene expression patterns in diverse maize hybrids during root development},
volume = {71},
year = {2020}
}
|
|
Jan Philip Oeyen, Patrice Baa-Puyoulet, Joshua B. Benoit, Leo W. Beukeboom, Erich Bornberg-Bauer, Anja Buttstedt, Federica Calevro, Elizabeth I. Cash, Hsu Chao, Hubert Charles, Mei-Ju May Chen, Christopher Childers, Andrew G. Cridge, Peter Dearden, Huyen Dinh, Harsha Vardhan Doddapaneni, Amanda Dolan, Alexander Donath, Daniel Dowling, Shannon Dugan, Elizabeth Duncan, Elena N. Elpidina, Markus Friedrich, Elzemiek Geuverink, Joshua D. Gibson, Sonja Grath, Cornelis J. P. Grimmelikhuijzen, Ewald Große-Wilde, Cameron Gudobba, Yi Han, Bill S. Hansson, Frank Hauser, Daniel S. T. Hughes, Panagiotis Ioannidis, Emmanuelle Jacquin-Joly, Emily C. Jennings, Jeffery W. Jones, Steffen Klasberg, Sandra L. Lee, Peter Lesný, Mackenzie Lovegrove, Sebastian Martin, Alexander G. Martynov, Christoph Mayer, Nicolas Montagné, Victoria C. Moris, Monica Munoz-Torres, Shwetha Canchi Murali, Donna M. Muzny, Brenda Oppert, Nicolas Parisot, Thomas Pauli, Ralph S. Peters, Malte Petersen, Christian Pick, Emma Persyn, Lars Podsiadlowski, Monica F. Poelchau, Panagiotis Provataris, Jiaxin Qu, Maarten J. M. F. Reijnders, Björn Marcus von Reumont, Andrew J. Rosendale, Felipe A. Simao, John Skelly, Alexandros G. Sotiropoulos, Aaron L. Stahl, Megumi Sumitani, Elise M. Szuter, Olivia Tidswell, Evangelos Tsitlakidis, Lucia Vedder, Robert M. Waterhouse, John H. Werren, Jeanne Wilbrandt, Kim C. Worley, Daisuke S. Yamamoto, Louis van de Zande, Evgeny M. Zdobnov, Tanja Ziesmann, Richard A. Gibbs, Stephen Richards, Masatsugu Hatakeyama, Bernhard Misof, and Oliver Niehuis. Sawfly genomes reveal evolutionary acquisitions that fostered the mega-radiation of parasitoid and eusocial hymenoptera. Genome biology and evolution, 12(7):1099-1188, 2020.
abstract
doi
bibtex
|
| The tremendous diversity of Hymenoptera is commonly attributed to the evolution of parasitoidism in the last common ancestor of parasitoid sawflies (Orussidae) and wasp-waisted Hymenoptera (Apocrita). However, Apocrita and Orussidae differ dramatically in their species richness, indicating that the diversification of Apocrita was promoted by additional traits. These traits have remained elusive due to a paucity of sawfly genome sequences, in particular those of parasitoid sawflies. Here, we present comparative analyses of draft genomes of the primarily phytophagous sawfly Athalia rosae and the parasitoid sawfly Orussus abietinus. Our analyses revealed that the ancestral hymenopteran genome exhibited traits that were previously considered unique to eusocial Apocrita (e.g., low transposable element content and activity) and a wider gene repertoire than previously thought (e.g., genes for CO2 detection). Moreover, we discovered that Apocrita evolved a significantly larger array of odorant receptors than sawflies, which could be relevant to the remarkable diversification of Apocrita by enabling efficient detection and reliable identification of hosts. @article{Vedder2020b,
abstract = {The tremendous diversity of Hymenoptera is commonly attributed to the evolution of parasitoidism in the last common ancestor of parasitoid sawflies (Orussidae) and wasp-waisted Hymenoptera (Apocrita). However, Apocrita and Orussidae differ dramatically in their species richness, indicating that the diversification of Apocrita was promoted by additional traits. These traits have remained elusive due to a paucity of sawfly genome sequences, in particular those of parasitoid sawflies. Here, we present comparative analyses of draft genomes of the primarily phytophagous sawfly Athalia rosae and the parasitoid sawfly Orussus abietinus. Our analyses revealed that the ancestral hymenopteran genome exhibited traits that were previously considered unique to eusocial Apocrita (e.g., low transposable element content and activity) and a wider gene repertoire than previously thought (e.g., genes for CO2 detection). Moreover, we discovered that Apocrita evolved a significantly larger array of odorant receptors than sawflies, which could be relevant to the remarkable diversification of Apocrita by enabling efficient detection and reliable identification of hosts.},
author = {Oeyen, Jan Philip and Baa-Puyoulet, Patrice and Benoit, Joshua B. and Beukeboom, Leo W. and Bornberg-Bauer, Erich and Buttstedt, Anja and Calevro, Federica and Cash, Elizabeth I. and Chao, Hsu and Charles, Hubert and Chen, Mei-Ju May and Childers, Christopher and Cridge, Andrew G. and Dearden, Peter and Dinh, Huyen and Doddapaneni, Harsha Vardhan and Dolan, Amanda and Donath, Alexander and Dowling, Daniel and Dugan, Shannon and Duncan, Elizabeth and Elpidina, Elena N. and Friedrich, Markus and Geuverink, Elzemiek and Gibson, Joshua D. and Grath, Sonja and Grimmelikhuijzen, Cornelis J. P. and Gro{\ss}e-Wilde, Ewald and Gudobba, Cameron and Han, Yi and Hansson, Bill S. and Hauser, Frank and Hughes, Daniel S. T. and Ioannidis, Panagiotis and Jacquin-Joly, Emmanuelle and Jennings, Emily C. and Jones, Jeffery W. and Klasberg, Steffen and Lee, Sandra L. and Lesn{\'y}, Peter and Lovegrove, Mackenzie and Martin, Sebastian and Martynov, Alexander G. and Mayer, Christoph and Montagn{\'e}, Nicolas and Moris, Victoria C. and Munoz-Torres, Monica and Murali, Shwetha Canchi and Muzny, Donna M. and Oppert, Brenda and Parisot, Nicolas and Pauli, Thomas and Peters, Ralph S. and Petersen, Malte and Pick, Christian and Persyn, Emma and Podsiadlowski, Lars and Poelchau, Monica F. and Provataris, Panagiotis and Qu, Jiaxin and Reijnders, Maarten J. M. F. and von Reumont, Bj{\"o}rn Marcus and Rosendale, Andrew J. and Simao, Felipe A. and Skelly, John and Sotiropoulos, Alexandros G. and Stahl, Aaron L. and Sumitani, Megumi and Szuter, Elise M. and Tidswell, Olivia and Tsitlakidis, Evangelos and Vedder, Lucia and Waterhouse, Robert M. and Werren, John H. and Wilbrandt, Jeanne and Worley, Kim C. and Yamamoto, Daisuke S. and {van de Zande}, Louis and Zdobnov, Evgeny M. and Ziesmann, Tanja and Gibbs, Richard A. and Richards, Stephen and Hatakeyama, Masatsugu and Misof, Bernhard and Niehuis, Oliver},
doi = {10.1093/gbe/evaa106},
journal = {Genome biology and evolution},
number = {7},
pages = {1099--1188},
title = {Sawfly Genomes Reveal Evolutionary Acquisitions That Fostered the Mega-Radiation of Parasitoid and Eusocial Hymenoptera},
volume = {12},
year = {2020}
}
|
|
E. Lehndorff, N. Meyer, A. Radionov, L. Plümmer, P. Rottmann, B. Spiering, W. Amelung, and S. Dultz. Spatial organization of soil microaggregates. In EGU General Assembly Conference Abstracts, pages 22405. 2020.
abstract
bibtex
|
| The physical arrangement of soil compounds in microaggregates is important in many ways, e.g. by controlling soil stability and C sequestration. However, little is known about the spatial arrangement of organic and inorganic compounds in soil microaggregates, due to the lack of in-situ analyses in undisturbed material. Here we hypothesize that microaggregates are spatially organized, resulting in deterministic, predictable spatial patterns of different organic matter and mineral phases and that this organization depends on the abundance of specific phases such as on clay mineral content. We separated the water stable, occluded large and small microaggregate fractions from Ap horizons of a sequence of sandy to loamy Luvisols (19 to 35% clay, Scheyern, Germany) and subjected in total 60 individual aggregates to elemental mapping by electron probe micro analysis (EPMA), which recorded C, N, P, Al, Fe, Ca, K, Cl, and Si contents at µm scale resolution. Spatial arrangements of soil organic matter and soil minerals were extracted using cluster analyses. We found a pronounced heterogeneity in aggregate structure and composition, which was not reproducible and largely independent from clay content in soil. However, neighborhood analyses revealed close spatial correlations between organic matter debris (C:N app. 100:10) and microbial organic matter (C:N app. 10:1) indicating a spatial relationship between source and consumer. There was no systematic relationship between soil minerals and organic matter, suggesting that well-established macroscale correlations between contents of pedogenic oxides and clay minerals with soil organic matter storage do not apply to soil microaggregates. @inproceedings{lehndorff2020spatial,
abstract = {The physical arrangement of soil compounds in microaggregates is important in many ways, e.g. by controlling soil stability and C sequestration. However, little is known about the spatial arrangement of organic and inorganic compounds in soil microaggregates, due to the lack of in-situ analyses in undisturbed material. Here we hypothesize that microaggregates are spatially organized, resulting in deterministic, predictable spatial patterns of different organic matter and mineral phases and that this organization depends on the abundance of specific phases such as on clay mineral content. We separated the water stable, occluded large and small microaggregate fractions from Ap horizons of a sequence of sandy to loamy Luvisols (19 to 35% clay, Scheyern, Germany) and subjected in total 60 individual aggregates to elemental mapping by electron probe micro analysis (EPMA), which recorded C, N, P, Al, Fe, Ca, K, Cl, and Si contents at µm scale resolution. Spatial arrangements of soil organic matter and soil minerals were extracted using cluster analyses. We found a pronounced heterogeneity in aggregate structure and composition, which was not reproducible and largely independent from clay content in soil. However, neighborhood analyses revealed close spatial correlations between organic matter debris (C:N app. 100:10) and microbial organic matter (C:N app. 10:1) indicating a spatial relationship between source and consumer. There was no systematic relationship between soil minerals and organic matter, suggesting that well-established macroscale correlations between contents of pedogenic oxides and clay minerals with soil organic matter storage do not apply to soil microaggregates.},
author = {Lehndorff, E. and Meyer, N. and Radionov, A. and Pl{\"u}mmer, L. and Rottmann, P. and Spiering, B. and Amelung, W. and Dultz, S.},
booktitle = {EGU General Assembly Conference Abstracts},
pages = {22405},
title = {Spatial organization of soil microaggregates},
year = {2020}
}
|