ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Snap Rounding with Restore

This article presents a new algorithm called Snap Rounding with Restore (SRR), which aims to make geometric datasets robust and to increase the quality of geometric approximation and the preservation of topological structure. It is based on the well-known Snap Rounding algorithm but improves it by eliminating from the snap rounded arrangement the... (more)

Area-Preserving Simplification and Schematization of Polygonal Subdivisions

In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm... (more)

Spatial Consensus Queries in a Collaborative Environment

We introduce a new type of query for a location-based social network platform. Consider a scenario in which a group of users is trying to find a... (more)

Privacy-Aware Dynamic Ride Sharing

Dynamic ride sharing is a service that enables shared vehicle rides in real time and on short notice. It can be an effective solution to counter the problem of increasing traffic jams at peak hours in cities. The growing use and popularity of smart phones and GPS-enabled devices provides us with tools required to efficiently implement ride sharing... (more)


About TSAS

ACM Transactions on Spatial Algorithms and Systems (TSAS) is a new scholarly journal that publishes high-quality papers on all aspects of spatial algorithms and systems and closely related disciplines. It has a multi-disciplinary perspective spanning a large number of areas where spatial data is manipulated or visualized (regardless of how it is specified - i.e., geometrically or textually), such
as: geography, geographic information systems (GIS), geospatial and spatiotemporal databases, spatial and metric indexing, location-based services, web-based spatial applications, geographic information retrieval (GIR), spatial reasoning and mining, security and privacy, as well as the related visual computing areas of computer graphics, computer vision, solid modeling, and visualization where the spatial, geospatial, and spatiotemporal data is central.  READ MORE

Call-for-papers: ACM TSAS has issued a call for papers for its inaugural issue.
Please use manuscriptcentral ( to submit articles, check the status of articles and for reviewing tasks.

New options for ACM authors to manage rights and permissions for their work

ACM introduces a new publishing license agreement, an updated copyright transfer agreement, and a new author-pays option which allows for perpetual open access through the ACM Digital Library. For more information, visit the ACM Author Rights webpage.

Forthcoming Articles
Location Estimation Using Crowdsourced Spatial Relations

The ``crowd'' has become a very important geospatial data provider. Subsumed under the term Volunteered Geographic Information (VGI), non-expert users have been providing a wealth of quantitative geospatial data online. With spatial reasoning being a basic form of human cognition, narratives expressing geospatial experiences, e.g., travel blogs, would provide an even bigger source of geospatial data. Textual narratives typically contain qualitative data in the form of objects and spatial relationships. The scope of this work is (i) to extract these relationships from user-generated texts, (ii) to quantify them and (iii) to reason about object locations based only on this qualitative data. We use information extraction methods to identify toponyms and spatial relationships and we formulate a quantitative approach based on distance and orientation features to represent the latter. Positional probability distributions for spatial relationships are determined by means of a greedy Expectation Maximization-based (EM) algorithm. These estimates are then used to ``triangulate'' the positions of unknown object locations. Experiments using a text corpus harvested from travel blog sites establish the considerable location estimation accuracy of the proposed approach on synthetic and real world scenarios.

Protecting Against Velocity-based, Proximity-based and External Event Attacks in Location-Centric Social Networks

An efficient external memory algorithm for terrain viewshed computation

This paper presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too large for internal memory, even over 100000x100000 points. It subdivides the terrain into tiles, that are stored compressed on disk and then paged into memory with a custom cache data structure and LRU algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TiledVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all the terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TiledVS is very fast, for instance, processing a 104000x104000 terrain on a modest computer with only 512MB of RAM took only 1.5 hours. On large datasets, TiledVS was several times faster than competing algorithms such as are in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. An earlier version of this algorithm was published in a 4-page ACM SIGSPATIAL 2012 conference paper. This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons.


Publication Years 2015-2016
Publication Count 12
Citation Count 1
Available for Download 12
Downloads (6 weeks) 273
Downloads (12 Months) 1369
Downloads (cumulative) 1369
Average downloads per article 114
Average citations per article 0
First Name Last Name Award

First Name Last Name Paper Counts
Lars Kulik 2
Mauro Negri 1
Kyle Hickmann 1
Carola Wenk 1
Bettina Speckmann 1
Peter Scheuermann 1
Cyrus Shahabi 1
Yi Yu 1
Preeti Goel 1
Martin Nöllenburg 1
Sara Migliorini 1
Maria Damiani 1
Sadao Obana 1
Karine Zeitouni 1
André Van Renssen 1
Suhua Tang 1
Janne Kovanen 1
Mohammed Ali 1
Sarana Nutanong 1
Leyla Kazemi 1
Mark Mckennney 1
Andreas Gemsa 1
Jan Haunert 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Roger Frye 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Hien To 1
Dai That 1
Mahmuda Ahmed 1
Brittany Fasy 1
Roger Zimmermann 1
Tapani Sarjakoski 1
Iulian Popa 1
Kevin Buchin 1
Fabio Valdes 1
Wouter Meulemans 1
Alberto Belussi 1

Affiliation Paper Counts
University of Texas at San Antonio 1
Northwestern University 1
University of Milan 1
Microsoft 1
City University London 1
Bangladesh University of Engineering and Technology 1
National University of Singapore 1
City University of Hong Kong 1
University of Osnabruck 1
Politecnico di Milano 2
University of Verona 2
University of Electro-Communications 2
University of Hagen 2
Research Organization of Information and Systems National Institute of Informatics 2
Southern Illinois University at Edwardsville 2
Eindhoven University of Technology 2
Karlsruhe Institute of Technology 2
University of Southern California 2
Universite de Versailles Saint-Quentin-en-Yvelines 3
Tulane University 3
University of Melbourne 5

ACM Transactions on Spatial Algorithms and Systems

Volume 2 Issue 1, April 2016

Volume 1 Issue 2, November 2015
Volume 1 Issue 1, August 2015 Inaugural Issue
All ACM Journals | See Full Journal Index