NDLI: On IO-efficient viewshed algorithms and their accuracy

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

Sweeping a terrain by collaborative aerial vehicles

An opportunistic client user interface to support centralized ride share planning

Spatiotemporal Braitenberg vehicles

Efficient batch processing of proximity queries by optimized probing

Parameterized algorithms for generalized traveling salesman problems in road networks

Finding competitive price

GeoRank: an efficient location-aware news feed ranking system

Large-scale joint map matching of GPS traces

Morphologically-aware elimination of flat edges from a TIN

A parallel spatial data analysis infrastructure for the cloud

GeoTruCrowd: trustworthy query answering with spatial crowdsourcing

iGSLR: personalized geo-social location recommendation: a kernel density estimation approach

Tag configuration matcher for geo-tagging

A spatial keyword evaluation framework for network-based spatial queries

Point-polygon topological relationship query using hierarchical indices

Computing highly occluded paths on a terrain

Evaluating eco-driving advice using GPS/CANBus data

Supporting topological relationship queries for complex line and collection geometries in oracle spatial

Efficient proximity detection among mobile objects in road networks with self-adjustment methods

Dejavu: an accurate energy-efficient outdoor localization system

Spatio-temporal characteristics of bursty words in Twitter streams

Efficient geometric graph matching using vertex embedding

Algorithms for Computing Prominence on Grid Terrains

CG_Hadoop: computational geometry in MapReduce

Maximizing the number of worker's self-selected tasks in spatial crowdsourcing

Crowd sensing of traffic anomalies based on human mobility and social media

Point of interest to region of interest conversion

Safe step: a real-time gps tracking and analysis system for criminal activities using ankle bracelets

Edge-based locality sensitive hashing for efficient geo-fencing application

On IO-efficient viewshed algorithms and their accuracy

Energy-optimal routes for electric vehicles

A filter-and-refine approach to mine spatiotemporal co-occurrences

Algorithms for hotspot computation on trajectory data

Routing directions: keeping it fast and simple

A spatiotemporal scientometrics framework for exploring the citation impact of publications and scientists

Model-driven matching and segmentation of trajectories

Efficient identification and approximation of k-nearest moving neighbors

Robust and efficient polygon overlay on parallel stream processors

Output-sensitive well-separated pair decompositions for dynamic point sets

Pathlet learning for compressing and planning trajectories

A graph-based model for the representation of land spaces

Quick geo-fencing using trajectory partitioning and boundary simplification

Analysis and evaluation of the slugging form of ridesharing

SAC: semantic adaptive caching for spatial mobile applications

A probablistic model for spatio-temporal signal extraction from social media

CALBA: capacity-aware location-based advertising in temporary social networks

Trajectory based optimal segment computation in road network databases

Mining group movement patterns

ACM SIGSPATIAL GIS Cup 2013: geo-fencing

Location recommendation in location-based social networks using user check-in data

Orientation data correction with georeferenced mobile videos

Augmented navigation in outdoor environments

Efficient storage and retrieval of geo-referenced video from moving sensors

Demonstration of Hadoop-GIS: a spatial data warehousing system over MapReduce

Using extrusion to generate higher-dimensional GIS datasets

GeoWhiz: toponym resolution using common categories

Efficient algorithms for spatial skyline query with uncertainty

Trajectory based traffic analysis

Online, deviation-constrained capacitated vehicle routing

Haze: privacy-preserving real-time traffic statistics

Consuming web services on mobile devices for improved mHealth

GIVA: a semantic framework for geospatial and temporal data integration, visualization, and analytics

Geo-coding scheme for multimedia in indoor space

Isochrones, traffic and DEMOgraphics

Accentuating focus maps via partial schematization

TrajMetrix: a trajectory compression benchmarking framework

A privacy-preserving location-based alert system

A carpooling recommendation system based on social VANET and geo-social data

Representing positional uncertainty of individual and aggregated trajectories of moving objects

Kongress: a search and data mining application for U.S. congressional voting and Twitter data

Weighted multi-attribute matching of user-generated points of interest

The MGIS: a minimal geographic information system accessible to users who are blind

Map matching: comparison of approaches using sparse and noisy data

A 3D geospatial registration service for street level covisualization of 2D vector maps

Mining large-scale gps streams for connectivity refinement of road maps

Probabilistic parking queries using aging functions

Computing similarity of coarse and irregular trajectories using space-time prisms

Segmentation-based road network construction

A graph model for false negative handling in indoor RFID tracking data

On robust interpretation of topological relations in identity and tolerance models

Capturing hotspots for constrained indoor movement

Improving route prediction through user journey detection

Image driven GPS trace analysis for road map inference

Map matching: facts and myths

Using eye movements to recognize activities on cartographic maps

Minimal spatio-temporal database repairs

Thrifty tracking: online GPS tracking with low data uplink usage

Customizable point-of-interest queries in road networks

Locating lucrative passengers for taxicab drivers

On IO-efficient viewshed algorithms and their accuracy

Content Provider	ACM Digital Library
Author	Toma, Laura Wei, Bob PoFang Haverkort, Herman
Abstract	Given a terrain T and a point v, the viewshed or visibility map of v is the set of points in T that are visible from v. To decide whether a point p is visible one needs to interpolate the elevation of the terrain along the line-of-sight (LOS) vp. Existing viewshed algorithms differ widely in which and how many points they chose to interpolate, how many lines-of-sight they consider, and how they interpolate the terrain. These choices crucially affect the running time and accuracy of the algorithms. In this paper our goal was to obtain an IO-efficient algorithm that computes the viewshed on a grid terrain with as much accuracy as possible given the resolution of the data. We describe two algorithms which are based on computing and merging horizons, and we prove that the complexity of horizons on a grid of n points is O(n), improving on the general O(nα(n)) bound on triangulated terrains. Our finding is that, in practice, horizons on grids are significantly smaller than their theoretical worst case bound, which makes horizon-based approaches very fast. To measure the differences between viewsheds computed with various algorithms we implement an error metric that averages differences over a large number of viewsheds computed from a set of viewpoints with topological significance, like valleys and ridges. Using this metric we compare our current approach, Van Kreveld's model used in our previous work [7], the algorithm of Ferreira et al. [6], and the viewshed module r.los in the open source GIS GRASS.
Starting Page	24
Ending Page	33
Page Count	10
File Format	PDF
ISBN	9781450325219
DOI	10.1145/2525314.2525369
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-11-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Io-model Terrain Grid Visibility
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