NDLI: Exact and approximate computations of watersheds on triangulated terrains

Please wait, while we are loading the content...

Geometric overpass extraction from vector road data and DSMs

Pedestrian-movement prediction based on mixed Markov-chain model

TerraNNI: natural neighbor interpolation on a 3D grid using a GPU

What you are is when you are: the temporal dimension of feature types in location-based social networks

A splitting line model for directional relations

Finding the most accessible locations: reverse path nearest neighbor query in road networks

EnAcq: energy-efficient GPS trajectory data acquisition based on improved map matching

A new method for subdivision simplification with applications to urban-area generalization

Parking slot assignment games

Learning to resolve geographical and temporal references in text

A visual analytics system for metropolitan transportation

Planar roof surface segmentation using 3D vision

Semantic trajectory mining for location prediction

Exact and approximate computations of watersheds on triangulated terrains

Learning location naming from user check-in histories

A kinematics-based GIS methodology to represent and analyze spatiotemporal patterns of precipitation change in IPCC A2 scenario

On efficient obstructed reverse nearest neighbor query processing

Privacy-preserving assessment of location data trustworthiness

Delineating imprecise regions via shortest-path graphs

Constructing geo-ontologies by reification of observation data

Range query processing in multi-objective networks

SpSJoin: parallel spatial similarity joins

3D building roof reconstruction from point clouds via generative models

Discovering interesting sub-paths in spatiotemporal datasets: a summary of results

Flow on noisy terrains: an experimental evaluation

A neighborhood graph based approach to regional co-location pattern discovery: a summary of results

Kinetic space-time prisms

Multi-approximate-keyword routing in GIS data

Median trajectories using well-visited regions and shortest paths

Conflation of road network and geo-referenced image using sparse matching

Path shapes: an alternative method for map matching and fully autonomous self-localization

Where traffic meets DNA: mobility mining using biological sequence analysis revisited

ASSIST: access controlled ship identification streams

Transportation mode detection using mobile phones and GIS information

The PR-star octree: a spatio-topological data structure for tetrahedral meshes

Similarity search on a large collection of point sets

Evaluating and minimizing ambiguities in qualitative route instructions

Fast GPU-based locality sensitive hashing for k-nearest neighbor computation

Data-driven trajectory smoothing

Boundary-labeling algorithms for panorama images

Exploration and comparison of geographic information sources using distance statistics

Scalable local regression for spatial analytics

Searching web documents as location sets

Prox-RBAC: a proximity-based spatially aware RBAC

Private geosocial networking

Overlapping and synchronizing two worlds

Instant approximate 1-center on road networks via embeddings

An experimental virtual museum based on augmented reality and navigation

Identifying destinations automatically from human generated route directions

A trajectory correlation algorithm based on users' daily routines

Location recommendation based on location history and spatio-temporal correlations for an on-demand bus system

Exploring spatiotemporal patterns by integrating visual analytics with a moving objects database system

Frequent route based continuous moving object location- and density prediction on road networks

Jeocrowd: collaborative searching of user-generated point datasets

Spatial and spatiotemporal analysis of soccer

Real-time routing with OpenStreetMap data

Progressive spatial join for polygon data stream

TARSIUS: a system for traffic-aware route search under conditions of uncertainty

Energy-efficient shortest path query processing on air

CROWDSAFE: crowd sourcing of crime incidents and safe routing on mobile devices

Extracting patterns from location history

Porting a web-based mapping application to a smartphone app

Unveiling locations in geo-spatial documents

mTrend: discovery of topic movements on geo-microblogging messages

A greener transportation mode: flexible routes discovery from GPS trajectory data

PedSeg: GPS tracks as priors for overhead image segmentation

The design of a benchmark for geo-stream management systems

Trip analyzer through smartphone apps

A unified framework for decentralized reasoning about gradual changes in topological relations

Exploring map-based interactions for co-located collaborative work by multiple mobile users

Exploration through enrichment: a visual analytics approach for animal movement

Learning boundaries of vague places from noisy annotations

An inference system for relationships between spatial granularities

Exploring dynamic fan shapes for nearby traffic monitoring queries in road networks

Simplifying morphological representations of 2D and 3D scalar fields

LOCAR: local compression of alternative routes

Learning to associate relevant photos to georeferenced textual documents

Characterizing sensor datasets with multi-granular spatio-temporal intervals

Towards integrating real-world spatiotemporal data with social networks

Parallel quadtree coding of large-scale raster geospatial data on GPGPUs

Bernoulli trials based feature selection for crater detection

Spatial categorical outlier detection: pair correlation function based approach

Engineering efficient error-correcting geocoding

Geospatial overlay computation on the GPU

Exact and approximate computations of watersheds on triangulated terrains

Content Provider	ACM Digital Library
Author	de Berg, Mark Tsirogiannis, Constantinos
Abstract	The natural way of modeling water flow on a triangulated terrain is to make the fundamental assumption that water follows the direction of steepest descent (dsd). However, computing watersheds and other flow-related structures according to the dsd model in an exact manner is difficult: the dsd model implies that water does not necessarily follow terrain edges, which makes designing exact algorithms difficult and causes robustness problems when implementing them. As a result, existing software implementations for computing watersheds are inexact: they either assume a simplified flow model or they perform computations using inexact arithmetic, which leads to inexact and sometimes inconsistent results. We perform a detailed study of various issues concerning the exact or approximate computation of watersheds according to the dsd model. Our main contributions are the following. • We provide the first implementation that computes watersheds on triangulated terrains following strictly the dsd model and using exact arithmetic, and we experimentally investigate its computational cost. Our experiments show that the algorithm cannot handle large data sets effectively, due to the bit-sizes needed in the exact computations and the computation of an intermediate structure called the strip map. • Using our exact algorithm as a point of reference, we evaluate the quality of several existing heuristics for computing watersheds. We also investigate hybrid methods, which use heuristics in a first phase of the algorithm and exact computation in a second phase. The hybrid methods are almost as fast as the heuristics, but give significantly more accurate results. • We describe and theoretically analyze a new exact algorithm for computing watersheds, which avoids the computation of the strip map.
Starting Page	74
Ending Page	83
Page Count	10
File Format	PDF
ISBN	9781450310314
DOI	10.1145/2093973.2093985
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-11-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in