Scatter plots are diagrams that visualize sets of points in two dimensions. They allow users to detect correlations and clusters in the data. Whether a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot has some nice geometric property, e.g., a large minimum angle or a small total edge length. In order to find an optimum aspect ratio according to a given criterion we present an algorithm that efficiently maintains the Delaunay triangulation of the point set when traversing all aspect ratios

@inproceedings{FinkEtAl2013,
    abstract = {Scatter plots are diagrams that visualize sets of points in two dimensions. They allow users to detect correlations and clusters in the data. Whether a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot has some nice geometric property, e.g., a large minimum angle or a small total edge length. In order to find an optimum aspect ratio according to a given criterion we present an algorithm that efficiently maintains the Delaunay triangulation of the point set when traversing all aspect ratios},
    author = {Fink, M. and Haunert, J.-H. and Spoerhase, J. and Wolff, A.},
    booktitle = {Proc. 29th European Workshop on Computational Geometry (EuroCG'13)},
    timestamp = {2013-01-29T14:57:50.000+0100},
    title = {Selecting the Aspect Ratio of a Scatter Plot Based on Its {D}elaunay Triangulation},
    year = {2013}
}

Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.

doi:10.1109/TVCG.2013.187

@article{FinkEtAl2013b,
    abstract = {Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.},
    author = {Fink, M. and Haunert, J.-H. and Spoerhase, J. and Wolff, A.},
    doi = {10.1109/TVCG.2013.187},
    journal = {IEEE Transactions on Visualization and Computer Graphics)},
    number = {12},
    pages = {2326--2335},
    timestamp = {2013-07-25T18:19:08.000+0200},
    title = {Selecting the Aspect Ratio of a Scatter Plot Based on Its {D}elaunay Triangulation},
    volume = {19},
    year = {2013}
}

@phdthesis{Haunert2013b,
    author = {Haunert, J.-H.},
    file = {Haunert_Habil.pdf:http\://www1.pub.informatik.uni-wuerzburg.de/pub/haunert/pdf/Haunert_Habil.pdf:PDF},
    school = {Fakult\"{a}t f\"{u}r Mathematik und Informatik},
    series = {Universit\"{a}t W\"{u}rzburg},
    timestamp = {2013-07-25T14:07:36.000+0200},
    title = {An Algorithmic Approach to Geographic Information Science},
    type = {Habilitationsschrift (kumulativ)},
    year = {2013}
}

@inproceedings{Peng2013,
    author = {Peng, D. and Haunert, J.-H. and Wolff, A. and Hurter, C.},
    booktitle = {Proc. 16th ICA Generalisation Workshop},
    timestamp = {2013-05-13T17:21:59.000+0200},
    title = {Morphing Polylines Based on Least-Squares Adjustment},
    year = {2013}
}

@inproceedings{Schwartges2013,
    author = {Schwartges, Nadine and Allerkamp, Dennis and Haunert, J.-H. and Wolff, A.},
    booktitle = {Proc. 16th ICA Generalisation Workshop},
    timestamp = {2013-05-13T17:07:20.000+0200},
    title = {Optimizing Active Ranges for Point Selection in Dynamic Maps},
    year = {2013}
}

We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.

doi:10.1145/2525314.2525452

@inproceedings{vanDijkEtAl2013,
    abstract = {We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.},
    author = {T. C. van Dijk and A. van Goethem and J.-H. Haunert and W. Meulemans and B. Speckmann},
    booktitle = {Proc. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '13)},
    doi = {10.1145/2525314.2525452},
    pages = {418--421},
    title = {Accentuating focus maps via partial schematization},
    year = {2013}
}

Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices.

doi:10.1007/978-3-642-37087-8_16

@inproceedings{VanDijkHaunert2013,
    abstract = {Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices.},
    author = {van Dijk, T. C. and Haunert, J.-H.},
    booktitle = {Proc. 12th International Symposium on Web and Wireless Geographical Information Systems (W2GIS'13)},
    doi = {10.1007/978-3-642-37087-8_16},
    pages = {214--222},
    timestamp = {2013-01-29T14:57:51.000+0100},
    title = {A probabilistic model for road selection in mobile maps},
    year = {2013}
}

In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.

doi:10.1145/2534931.2534936

@inproceedings{vanDijkHaunert2013b,
    abstract = {In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.},
    author = {van Dijk, T. C. and Fleszar, K. and Haunert, J.-H. and Spoerhase, J.},
    booktitle = {Proc. 1st ACM SIGSPATIAL Workshop on MapInteraction},
    doi = {10.1145/2534931.2534936},
    journal = {Unknown Journal},
    title = {Road segment selection with strokes and stability},
    year = {2013}
}

The acquisition of detailed information for buildings and their components becomes more and more important. However, an automatic reconstruction needs high-resolution measurements. Such features can be derived from images or 3D laserscans that are e.g. taken by unmanned aerial vehicles (UAV). Since this data is not always available or not measurable at the first for example due to occlusions we developed a reasoning approach that is based on sparse observations. It benefits from an extensive prior knowledge of probability density distributions and functional dependencies and allows for the incorporation of further structural characteristics such as symmetries. Bayesian networks are used to determine posterior beliefs. Stochastic reasoning is complex since the problem is characterized by a mixture of discrete and continuous parameters that are in turn correlated by nonlinear constraints. To cope with this kind of complexity, the implemented reasoner combines statistical methods with constraint propagation. It generates a limited number of hypotheses in a model-based top-down approach. It predicts substructures in building facades - such as windows - that can be used for specific UAV navigations for further measurements.

doi:10.5194/isprsarchives-XL-1-W2-257-2013

@inproceedings{isprs-archives-XL-1-W2-257-2013,
    abstract = {The acquisition of detailed information for buildings and their components becomes more and more important. However, an automatic reconstruction needs high-resolution measurements. Such features can be derived from images or 3D laserscans that are e.g. taken by unmanned aerial vehicles (UAV). Since this data is not always available or not measurable at the first for example due to occlusions we developed a reasoning approach that is based on sparse observations. It benefits from an extensive prior knowledge of probability density distributions and functional dependencies and allows for the incorporation of further structural characteristics such as symmetries. Bayesian networks are used to determine posterior beliefs. Stochastic reasoning is complex since the problem is characterized by a mixture of discrete and continuous parameters that are in turn correlated by nonlinear constraints. To cope with this kind of complexity, the implemented reasoner combines statistical methods with constraint propagation. It generates a limited number of hypotheses in a model-based top-down approach. It predicts substructures in building facades -- such as windows -- that can be used for specific UAV navigations for further measurements.},
    author = {Loch-Dehbi, S. and Dehbi, Y. and Pl\"umer, L.},
    booktitle = {Proc. UAV-g Conference 2013},
    doi = {10.5194/isprsarchives-XL-1-W2-257-2013},
    pages = {257--261},
    series = {ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences},
    title = {Stochastic reasoning for UAV supported reconstruction of 3D building models},
    url = {https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XL-1-W2/257/2013/},
    volume = {XL-1/W2},
    year = {2013}
}

@inproceedings{gnn-tbdml-13,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13)},
    title = {{Trajectory-Based Dynamic Map Labeling}},
    year = {2013}
}

@inproceedings{gnn-tbdml-isaac-13,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13)},
    file = {gnn-tbdml-isaac-13.pdf:http\://i11www.ira.uka.de/extra/publications/gnn-tbdml-isaac-13.pdf:PDF},
    note = {Full version available at http://arxiv.org/abs/1309.3963.},
    pages = {413--423},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Trajectory-Based Dynamic Map Labeling}},
    url = {http://dx.doi.org/10.1007/978-3-642-45030-3_39},
    volume = {8283},
    year = {2013}
}

@inproceedings{knrssw-tsbla-13,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    booktitle = {Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13)},
    title = {{Two-Sided Boundary Labeling with Adjacent Sides}},
    year = {2013}
}

@inproceedings{knrss-tsbla-13,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    booktitle = {Algorithms and Data Structures, 13th International Symposium (WADS'13)},
    pages = {463--474},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Two-Sided Boundary Labeling with Adjacent Sides}},
    volume = {8037},
    year = {2013}
}

@inproceedings{bbnnpr-uilps-13,
    author = {T. Biedl and T. Bl{\"a}sius and B. Niedermann and M. N{\"o}llenburg and R. Prutkin and I. Rutter},
    booktitle = {Proceedings of the 21st International Symposium on Graph Drawing (GD'13)},
    editor = {Stephen K. Wismath and A. Wolff},
    file = {bbnnpr-uilps-13.pdf:http\://i11www.ira.uka.de/extra/publications/bbnnpr-uilps-13.pdf:PDF},
    note = {Full version available at http://arxiv.org/abs/1308.6778.},
    pages = {460--471},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Using {ILP/SAT} to determine pathwidth, visibility representations, and other grid-based graph drawings}},
    url = {http://dx.doi.org/10.1007/978-3-319-03841-4_40},
    volume = {8242},
    year = {2013}
}