Deutsch Intern
    Chair of Computer Science I - Algorithms and Complexity

    Papers at ACM GIS'16


    In this year, the chair has two accepted submissions at ACM GIS 2016: a paper on route planning, and another paper on crowdsourcing on historical city maps. The conference takes place in San Francisco in early November.

    Sabine Storandt's Paper (a collaboration with Stefan Funke and Sören Laue) considers the topic of route planing:

    In a conventional route planning query, a user specifies the start and the destination in the road network and gets as a result the shortest path between those points.
    But many other criteria besides the route length might play a role for a user to prefer a certain route, as, e.g., fuel consumption, jam likeliness,  scenicness, number of turns, toll costs and many more. Specifying the importance of each criterion manually to get the best trade-off is a non-trivial, unintuitive and time consuming undertaking for a user. In the paper, we develop approaches that deduce such preferences automatically based on paths previously driven by the user. 

    The paper by Benedikt Budig and Thomas van Dijk (toghether with Fabian Feitsch and Mauricio Giraldo Arteaga) concerns itself with Smart Crowdsourcing in the context of a project at the New York Public Library:

    Over the course of three years, the New York Public Library has run a crowdsourcing project to extract polygonal representation of the building footprints from insurance atlases of the 19th and early-20th century. As is common in crowdsourcing projects, the overall problem was decomposed into small user tasks and each task was given to multiple users. In the case of polygons representing building footprints, it is unclear how best to integrate the answers into a majority vote: given a set of polygons ostensibly describing the same footprint, what is the consensus? We discuss desirable properties of such a "consensus polygon" and arrive at an efficient algorithm. We have manually evaluated the algorithm on approximately 3,000 polygons corresponding to 200 footprints and observe that our algorithmic consensus polygons are correct for 96% of the footprints whereas only 85% of the (input) user polygons are correct.