W. Randolph Franklin
HomePeople & publications

People & publications

Marcus Vinicius Alvim Andrade

Publications and presentations associated with this collaborator, with available abstracts, downloads, and citation records.

50publication entries

Marcus Vinicius Alvim Andrade

2020

  • Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters. J. Computer Aided Design, March 2020. online 2019-12-19. doi:https://doi.org/10.1016/j.cad.2019.102801.
    [details] [full text]
    Abstract
    We present 3D-EPUG-OVERLAY, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-OVERLAY combines 5 techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-OVERLAY is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-OVERLAY is also more memory efficient. In all test cases, 3D-EPUG-OVERLAY's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection.
    BibTeX
    @article{salles-exact-cad-2019,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters",
    journal = "J. Computer Aided Design",
    note = "online 2019-12-19",
    year = "2020",
    month = "March",
    volume = "120",
    doi = "https://doi.org/10.1016/j.cad.2019.102801",
    href = "\bibhref{232-salles-exact-cad-2019}",
    mykey = "recent marcus salles parallel overlay"
}

2018

  • W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Data structures for parallel spatial algorithms on large datasets (vision paper). In Proceedings of BigSpatial'18: 7th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. Seattle, USA, 6 Nov 2018.
    [details] [full text] [slides]
    Abstract
    This paper describes data structures and algorithms for efficient implementation of GIS operations for large datasets on multicore Intel CPUs and on NVIDA GPUs. Typical operations are boolean combinations of polygons and map overlay. Efficient parallelization prefers simple regular data structures, such as structures of arrays of plain old datatypes. Warps of 32 threads are required to execute the same instruction (or be idle). Ideally, the data used by adjacent threads is adjacent in memory. Minimizing storage is important, as is accessing it in a regular pattern. That disparages pointers, linked lists, and trees. That implies that explicitly representing global topology is bad. If using only local topological formulae is sufficient, then it will be much faster. E.g., for many operations on a 2-D map (aka planar graph), the set of oriented edges suffices. Each edge knows the locations of its endpoints and the ids of its adjacent polygons. Any mass operation, such as area computation or point location, can be implemented as a map-reduce. All these techniques also apply in 3D to CAD/CAM and additive manufacturing. Indeed they are more important there.
    BibTeX
    @inproceedings{par-ds-bigspatial-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Data Structures for Parallel Spatial Algorithms on Large Datasets (Vision paper)",
    address = "Seattle, {USA}",
    month = "6 Nov",
    booktitle = "Proceedings of {BigSpatial'18}: 7th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
    year = "2018",
    href = "\bibhrefpt{227-par-ds-bigspatial-2018}{227-par-ds-bigspatial-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/227-par-ds-bigspatial-2018-talk.pdf",
    mykey = "recent marcus salles topology parallel"
}
  • W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes (extended abstract). In 28th Annual Fall Workshop on Computational Geometry. Queens College, CUNY, New York City, 26–27 Oct 2018.
    [details] [full text]
    Abstract
    We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection . The full version of this paper is being presented at the 2018 International Meshing Roundtable; it is currently online at https://project.inria.fr/imr27/files/2018/09/1035.pdf.
    BibTeX
    @inproceedings{exact-fast-parallel-fwcg-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Exact fast parallel intersection of large 3-{D} triangular meshes (extended abstract)",
    booktitle = "28th Annual Fall Workshop on Computational Geometry",
    address = "Queens College, {CUNY}, New York City",
    year = "2018",
    month = "26--27 Oct",
    href = "\bibhref{229-exact-fast-parallel-fwcg-2018}",
    mykey = "recent marcus salles overlay parallel topology"
}
  • W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes. In 27th International Meshing Roundtable. Albuquerque, New Mexico, 2 Oct 2018.
    [details] [full text] [slides]
    Abstract
    We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay's result matched the reference solution. It is freely available for nonprofit research and education.
    BibTeX
    @inproceedings{exact-fast-parallel-imr-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Exact fast parallel intersection of large 3-{D} triangular meshes",
    booktitle = "27th International Meshing Roundtable",
    address = "Albuquerque, New Mexico",
    year = "2018",
    month = "2 Oct",
    href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
    mykey = "recent marcus salles overlay parallel",
    customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}

2017

  • Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. Fast exact parallel 3D mesh intersection algorithm using only orientation predicates. In 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017). Los Angeles Area, CA, USA, 7–10 Nov 2017.
    [details] [full text] [slides]
    Abstract
    We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in GIS, CAD and Additive Manufacturing, and was developed to process big datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation. Our preliminary implementation has intersected two objects totalling 8M triangles in 11 elapsed seconds on a dual 8-core Xeon. The competing LibiGL took 248 seconds and CGAL took 2726 seconds. Our software is freely available for nonprofit research.
    BibTeX
    @inproceedings{salles-parallel-mesh-sigspatial-2017,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "Fast exact parallel {3D} mesh intersection algorithm using only orientation predicates",
    year = "2017",
    month = "7--10 Nov",
    booktitle = "25th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2017)}",
    address = "{Los Angeles Area, CA, USA}",
    href = "\bibhrefpt{223-salles-parallel-mesh-sigspatial-2017}{223-salles-parallel-mesh-sigspatial-2017-talk.pdf}",
    mykey = "salles marcus parallel",
    customlinkslides = "https://wrfranklin.org/p/223-salles-parallel-mesh-sigspatial-2017-talk.pdf"
}
  • W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. 3D-EPUG-Overlay: intersecting very large 3D triangulations in parallel. In 2017 SIAM conference on industrial and applied geometry. Pittsburgh PA USA, 10–12 July 2017. (talk).
    [details] [slides]
    Abstract
    We present 3D-EPUG-Overlay, an algorithm and preliminary implementation for intersecting (aka overlaying) two 3D triangulations. This operation is important in processing large geometry datasets in additive manufacturing. Much of our algorithm is a sequence of map-reduce operations, and so is easily parallelizable. We completely avoid roundoff errors and the associated topological problems by computing with rational numbers. We will handle geometric degeneracies with Simulation of Simplicity (SoS). Our target architecture is an inexpensive workstation. We have a complete 2D implementation, which has overlaid two 2D maps maps, with a total of 54,000,000 vertices and 739,000 faces, in only 322 elapsed seconds (excluding I/O) on a dual 8-core 3.4GHz Intel Xeon workstation. That time is using 16 cores, and is 11x faster than using one core. Our 3D implementation is complete except for SoS. It processes two 3D objects with a total of 6,000,000 face triangles and 3,000,000 tetrahedra in 180 elapsed seconds on 16 cores. The parallel speedup for 16 cores is a factor of 13. The execution time is almost linear in the data size, and could process much larger datasets, perhaps billions of triangles. We anticipate being able to process much larger datasets than competing SW can, and for datasets small enough for others to process, that we will be much faster and more robust on special cases.
    BibTeX
    @inproceedings{x3d-epug-siam-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "{3D-EPUG-Overlay}: Intersecting very large {3D} triangulations in parallel",
    booktitle = "2017 {SIAM} conference on industrial and applied geometry",
    year = "2017",
    month = "10--12 July",
    address = "Pittsburgh PA USA",
    note = "(talk)",
    href = "\bibhrefat{219-3d-epug-siam-2017-abs}{219-3d-epug-siam-2017.pdf}",
    mykey = "overlay parallel marcus salles epug-overlay",
    customlinkslides = "https://wrfranklin.org/p/219-3d-epug-siam-2017.pdf"
}
  • W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. An exact and efficient 3D mesh intersection algorithm using only orientation predicates. In S3PM-2017: International Convention on Shape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium. Berkeley, California, USA, 19–23 June 2017. (poster).
    [details] [poster]
    Abstract
    We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in CAD and Additive Manufacturing, and was developed to process the largest datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation.
    BibTeX
    @inproceedings{mesh-orientation-s3pm-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "An exact and efficient {3D} mesh intersection algorithm using only orientation predicates",
    booktitle = "{S3PM-2017}: International Convention on Shape, Solid, Structure, \\& Physical Modeling, Shape Modeling International {(SMI-2017)} Symposium",
    month = "19--23 June",
    address = "Berkeley, California, USA",
    host = "International Computer Science Institute",
    year = "2017",
    note = "(poster)",
    href = "\bibhrefap{}{220-mesh-orientation-s3pm-2017.pdf}",
    mykey = "parallel marcus salles overlay epug-overlay",
    customlinkposter = "https://wrfranklin.org/p/220-mesh-orientation-s3pm-2017.pdf"
}

2016

  • Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. RBC. Revista Brasileira de Cartografia (Online), 68:1221–1230, 2016. online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.
    [details] [full text]
    Abstract
    This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.
    BibTeX
    @article{mauricio-rational-rbc-2016,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    journal = "RBC. Revista Brasileira de Cartografia (Online)",
    year = "2016",
    volume = "68",
    pages = "1221-1230",
    note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
    href = "\bibhref{221-mauricio-rational-rbc-2016}",
    mykey = "wenlili marcus salles parallel"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi. Exact intersection of 3D geometric models. In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).
    [details] [full text] [slides]
    Abstract
    This paper presents 3D-EPUG-OVERLAY , an exact and parallel algorithm for computing the intersection of 3D triangulated meshes, a problem with applications in several fields such as GIS and CAD. 3D-EPUG-OVERLAY presents several innovations: it employs exact arithmetic and, thus, the computations are completely exact, which avoids topological impossibilities that are often created by floating point arithmetic. Also, it uses a uniform grid to index the geometric data and was designed to be easily parallelizable. Furthermore, we propose the use of Simulation of Simplicity to effectively ensure that all the special cases are properly handled by the algorithm.
    BibTeX
    @inproceedings{salles-xsect-3d-geoinfo-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli and Gruppi, Maurício Gouvêa",
    title = "Exact intersection of {3D} geometric models",
    booktitle = "Geoinfo 2016, {XVII Brazilian} Symposium on GeoInformatics",
    year = "2016",
    month = "November",
    address = "Campos do Jordão, SP, Brazil",
    puburl = "\url{http://www.geoinfo.info/geoinfo\_series.htm}",
    publisher = "Instituto Nacional de Pesquisas Espaciais (Brasil)",
    mykey = "wenlili marcus salles parallel overlay epug-overlay",
    href = "\bibhrefpt{217-salles-xsect-3d-geoinfo-2016}{217-salles-xsect-3d-geoinfo-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/217-salles-xsect-3d-geoinfo-2016-talk.pdf"
}
  • Salles Viana Gomes de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus Vinicius Alvim Andrade. An efficient map-reduce algorithm for spatio-temporal analysis using spark (GIS Cup). In 5th GIS-focused algorithm competition, GISCup 2016, co-located with ACM SIGSPATIAL GIS. 2016. Winner (2nd place).
    [details] [full text] [slides]
    Abstract
    We present an efficient parallel algorithm for performing spatio-temporal analysis in a Spark cluster. It divides the spatio-temporal cube into partitions and uses these partitions as the elements of the Spark Resilient Distributed Datasets (RDDs). As a result, data presents a better locality and the overheads are smaller than the overheads observed when single cells are used as elements of the RDDs. When used to find hotspots in the NYC Yellowcab data, our algorithm is up to 52 times faster than algorithms using single cells RDDs.
    BibTeX
    @inproceedings{salles-giscup-2016,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus Vinicius Alvim",
    title = "An efficient map-reduce algorithm for spatio-temporal analysis using Spark ({GIS Cup})",
    note = "Winner (2nd place)",
    booktitle = "5th {GIS}-focused algorithm competition, {GISCup} 2016, co-located with {ACM SIGSPATIAL GIS}",
    year = "2016",
    href = "\bibhrefpt{215-salles-giscup-2016}{215-salles-giscup-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/215-salles-giscup-2016-talk.pdf",
    mykey = "marcus wenlili salles parallel sallesgiscup2016"
}
  • Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, Marcus V. A. Andrade, and David L. Hedin. 3D segmented ODETLAP compression. 2016.
    [details] [full text]
    Abstract
    We propose a segmented ODETLAP compression algorithm to increase speed, and show that it is usually better in the maximum absolute error than JP3D for 3D datasets. Overdetermined Laplacian partial differential equations (ODETLAP) is a spatial approximation and data compression method. We use the CUSP library to accelerate ODETLAP approximation and the speedup is about 7 times on a GPU over a CPU core. Segmented ODETLAP compression is faster and uses less memory than unsegmented ODETLAP compression. We use the algorithm to compress several atmospheric datasets and an MRI dataset. For evaluation, we also compress the datasets using JPEG 2000 Part 10 JP3D. The results show that the compressed size of the algorithm is about 60\% that of JP3D for the same maximum absolute error.
    BibTeX
    @misc{wenli-odetlap-2016,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Hedin, David L.",
    title = "{3D} Segmented {ODETLAP} Compression",
    booktitle = "(unpublished)",
    year = "2016",
    href = "\bibhref{212-wenli-odetlap-2016}",
    mykey = "wenlili marcus salles odetlap"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. PinMesh – Fast and exact 3D point location queries using a uniform grid. Computer & Graphics Journal, special issue on Shape Modeling International 2016, 58:1–11, August 2016. (online 17 May). Awarded a reproducibility stamp, \url http://www.reproducibilitystamp.com/. URL: http://www.sciencedirect.com/science/article/pii/S0097849316300607, doi:https://doi.org/10.1016/j.cag.2016.05.017.
    [details] [full text] [slides]
    Abstract
    This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multimaterial mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently handle the largest available meshes. Because of a 2-level uniform grid, the expected preprocessing time is linear in the input size, and the code parallelizes well on a shared memory machine. Querying time is almost independent of the dataset size. PinMesh uses exact arithmetic with rational numbers to prevent roundoff errors, and symbolic perturbation with Simulation of Simplicity (SoS) to handle geometric degeneracies or special cases. PinMesh is intended to be a subroutine in more complex algorithms. It can preprocess a dataset and perform 1 million queries up to 27 times faster than RCT (Relative Closest Triangle), the current fastest algorithm. Preprocessing a sample dataset with 50 million triangles took only 14 elapsed seconds on a 16-core Xeon processor. The mean query time was 0.6 microseconds.
    BibTeX
    @article{salles-pinmesh-smi-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "{PinMesh} -- {Fast} and exact {3D} point location queries using a uniform grid",
    journal = "{Computer \\& Graphics Journal}, special issue on {Shape Modeling International} 2016",
    year = "2016",
    volume = "58",
    pages = "1--11",
    month = "August",
    doi = "https://doi.org/10.1016/j.cag.2016.05.017",
    url = "http://www.sciencedirect.com/science/article/pii/S0097849316300607",
    href = "\bibhrefpt{209-salles-smi-pinmesh-2016}{209-salles-smi-pinmesh-2016-talk.pptx}",
    note = "(online 17 May). Awarded a reproducibility stamp, \url{http://www.reproducibilitystamp.com/}.",
    customlinkslides = "https://wrfranklin.org/p/209-salles-smi-pinmesh-2016-talk.pptx",
    mykey = "salles marcus wenlili pinmesh parallel sallespinmeshsmi2016"
}
  • Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, and W. Randolph Franklin. An efficient external memory algorithm for terrain viewshed computation. ACM Trans. on Spatial Algorithms and Systems, 2016. doi:https://doi.org/10.1145/2903206.
    [details] [full text]
    Abstract
    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 100 000 × 100 000 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 104000 x 104000 terrain on a modest computer with only 512MB of RAM took only 1 2 1 hours. On large datasets, TiledVS was several times faster than competing algorithms such as the ones included in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. A preliminary version of this algorithm appeared in a 4-page ACM SIGSPATIAL GIS 2012 conference paper “More efficient terrain viewshed computation on massive datasets using external memory”. This more detailed version adds the fast lossless compression stage that reduces the time by 30\% to 40\%, and many more experiments and comparisons.
    BibTeX
    @article{chaulio-tiledvs-tsas-2016,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. Randolph",
    title = "An efficient external memory algorithm for terrain viewshed computation",
    href = "\bibhref{197-chaulio-tiledvs-tsas-2016}",
    journal = "{ACM} Trans. on Spatial Algorithms and Systems",
    year = "2016",
    volume = "2",
    number = "2",
    doi = "https://doi.org/10.1145/2903206",
    mykey = "salles marcus visviewshedsiting tiledvs visibility"
}

2015

  • Mauricio G. Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. An efficient and topologically correct map generalization heuristic. In Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS), 516–525, paper 236. 2015. URL: http://www.iceis.org/Abstracts/2015/ICEIS_2015_Abstracts.htm, doi:https://doi.org/10.5220/0005398105160525.
    [details] [full text]
    Abstract
    We present TopoVW, an efficient heuristic for map simplification that deals with a variation of the generalization problem where the idea is to simplify the polylines of a map without changing the topological relationships between these polylines or between the lines and control points. This process is important for maintaining clarity of cartographic data, avoiding situations such as high density of map features, inappropriate intersections. In practice, high density of features may be represented by cities condensed into a small space on the map, inappropriate intersections may produce intersections between roads, rivers, and buildings. TopoVW is a strategy based on the Visvalingam-Whyatt algorithm to create simplified geometries with shapes similar to the original map, preserving topological consistency between features in the output. It uses a point ranking strategy, in which line points are ranked by their effective area, a metric that determines the impact a point will cause to the geometry if removed from the line. Points with inferior effective area are eliminated from the original line. The method was able to process a map with 4 million line points and 10 million control points in less than 2 minutes on a Intel Core 2 Duo processor.
    BibTeX
    @inproceedings{mauricio-iceis-2015,
    author = "Gruppi, Mauricio G. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "An Efficient and Topologically Correct Map Generalization Heuristic",
    booktitle = "Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS)",
    year = "2015",
    pages = "516-525, paper 236",
    doi = "https://doi.org/10.5220/0005398105160525",
    isbn = "978-989-758-096-3",
    mykey = "wenlili marcus salles",
    href = "\bibhref{214-mauricio-iceis-2015}",
    url = "http://www.iceis.org/Abstracts/2015/ICEIS\_2015\_Abstracts.htm"
}
  • Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 29 Nov – 2 Dec 2015.
    [details] [full text] [slides]
    Abstract
    This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speedup the process.
    BibTeX
    @inproceedings{mauricio-rational-geoinfo-2015,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    booktitle = "Geoinfo 2015, {XVI Brazilian} Symposium on GeoInformatics",
    year = "2015",
    month = "29 Nov -- 2 Dec",
    address = "Campos do Jordão, SP, Brazil",
    mykey = "marcus wenlili salles visviewshedsiting",
    href = "\bibhrefpt{198-mauricio-rational-geoinfo-2015}{198-mauricio-rational-geoinfo-2015-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/198-mauricio-rational-geoinfo-2015-talk.pdf"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS. Bellevue WA USA, 4 Nov 2015. Winner (2nd place).
    [details] [full text]
    BibTeX
    @inproceedings{salles-giscup-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast path planning under polygonal obstacle constraints",
    booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
    year = "2015",
    month = "4 Nov",
    address = "Bellevue WA USA",
    note = "Winner (2nd place)",
    mykey = "wenlili marcus salles pathplan sallesgiscup2015 uplan",
    href = "\bibhref{203-salles-giscup-2015}"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast exact parallel map overlay using a two-level uniform grid. In 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial). Bellevue WA USA, 3 Nov 2015. doi:https://doi.org/10.1145/2835185.2835188.
    [details] [full text]
    Abstract
    We present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with rational numbers, thereby ensuring exact computations with no roundoff errors and the ensuing sliver problems and topological impossibilities. For efficiency, EPUG-Overlay performs the map overlay in parallel, thereby utilizing the ubiquitous multicore architecture. Our application goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Indeed, overlaying two maps with 53,000,000 edges and 730,000 faces took only 322 elapsed seconds (plus 116 seconds for I/O) on a dual 8-core 3.1 GHz Intel Xeon E5-2687 workstation. In contrast, GRASS, executing sequentially and generating roundoff errors, takes 5300 seconds. The overlay operation combines two input maps (planar graphs) containing faces (polygons) separated by polyline edges (chains), into a new map, each of whose faces is the intersection of one face from each input map. Floating point roundoff errors can cause an edge intersection to be missed or the computed intersection point be in a wrong face, leading to a topological inconsistency. Thus, a program might fail to compute a valid output map at all, using any amount of time. This gets worse when the inputs are bigger or have slivers. Heuristics can ameliorate this problem, but only to an extent. By representing each coordinate as a vulgar fraction, with multiprecision numerator and denominator, the computation is exact. EPUG-Overlay also executes various useful subproblems very quickly, such as locating a set of points in a planar graph and finding all the intersections among a large set of small edges. EPUG-Overlay is built on our earlier sequential floating-point algorithm that found the areas of the overlay polygons, without finding the polygons themselves.
    BibTeX
    @inproceedings{salles-overlay-bigspatial-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast exact parallel map overlay using a two-level uniform grid",
    booktitle = "4th {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial)",
    year = "2015",
    month = "3 Nov",
    address = "Bellevue WA USA",
    href = "\bibhref{196-salles-overlay-bigspatial-2015}",
    doi = "https://doi.org/10.1145/2835185.2835188",
    mykey = "wenlili marcus salles overlay parallel"
}
  • Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient algorithm for computing the exact overlay of triangulations. In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).
    [details] [full text]
    BibTeX
    @inproceedings{salles-overlay-fwcg-2015,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient algorithm for computing the exact overlay of triangulations",
    booktitle = "25th Fall Workshop on Computational Geometry",
    year = "2015",
    month = "23-24 Oct",
    address = "U. Buffalo, New York, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles overlay",
    href = "\bibhref{201-salles-overlay-fwcg-2015}"
}
  • W. Randolph Franklin, Marcus Andrade, Wenli Li, and Salles de Magalhães. Changing problems, databases, and tools in spatial search. 24 Aug 2015. Talk at U. Zürich, Dept of Geography.
    [details] [slides]
    BibTeX
    @misc{changing-talk-zurich-2015,
    author = "Franklin, W. Randolph and Andrade, Marcus and Li, Wenli and de Magalhães, Salles",
    title = "Changing problems, databases, and tools in spatial search",
    note = "Talk at {U. Zürich}, {Dept} of {Geography}",
    month = "24 Aug",
    year = "2015",
    href = "\bibhreft{204-changing-talk-zurich-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/204-changing-talk-zurich-2015.pdf",
    mykey = "wenlili marcus salles parallel"
}
  • Marcus Andrade, Salles de Magalhães, W. Randolph Franklin, and Wenli Li. Research topics in GIS. Talk at CCNY, 15 April 2015.
    [details] [slides]
    BibTeX
    @misc{salles-ccny-2015,
    author = "Andrade, Marcus and de Magalhães, Salles and Franklin, W. Randolph and Li, Wenli",
    title = "Research topics in {GIS}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    href = "\bibhreft{194-salles-ccny-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/194-salles-ccny-2015.pdf",
    mykey = "marcus wenlili salles parallel"
}
  • Wenli Li, W. Randolph Franklin, Marcus Andrade, and Salles de Magalhães. Research summary: siting and ODETLAP. Talk at CCNY, 15 April 2015.
    [details] [slides]
    BibTeX
    @misc{wenli-ccny-2015,
    author = "Li, Wenli and Franklin, W. Randolph and Andrade, Marcus and de Magalhães, Salles",
    title = "Research Summary: Siting and {ODETLAP}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    mykey = "wenlili marcus salles odetlap",
    customlinkslides = "https://wrfranklin.org/p/193-wenli-ccny-2015.pdf",
    href = "\bibhreft{193-wenli-ccny-2015.pdf}"
}
  • Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Efficiently computing the drainage network on massive terrains with an external memory flooding process. Geoinformatica, April 2015. \url http://link.springer.com/article/10.1007/s10707-015-0225-y. doi:https://doi.org/10.1007/s10707-015-0225-y.
    [details] [full text]
    BibTeX
    @article{gomes-emflow-2015,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Efficiently computing the drainage network on massive terrains with an external memory flooding process",
    href = "\bibhref{163-gomes-emflow-2015}",
    journal = "Geoinformatica",
    doi = "https://doi.org/10.1007/s10707-015-0225-y",
    note = "\url{http://link.springer.com/article/10.1007/s10707-015-0225-y}",
    mykey = "marcus salles hydro emflow",
    month = "April",
    year = "2015"
}

2014

  • W. Randolph Franklin and Marcus Andrade. The changing problems, databases, and tools in spatial search. In University of California at Santa Barbara, Spatial Search Specialist Workshop. 8–9 Dec 2014.
    [details] [full text] [slides]
    BibTeX
    @inproceedings{ucsb-2014,
    author = "Franklin, W. Randolph and Andrade, Marcus",
    title = "The changing problems, databases, and tools in spatial search",
    booktitle = "{University of California at Santa Barbara, Spatial Search Specialist Workshop}",
    year = "2014",
    month = "8--9 Dec",
    customlinkslides = "https://wrfranklin.org/p/186-ucsb2014-spatial-probs-talk.pdf",
    mykey = "marcus",
    href = "\bibhrefpt{186-ucsb2014-spatial-probs}{186-ucsb2014-spatial-probs-talk.pdf}"
}
  • Salles V. G. de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus V. A. Andrade. Fast map generalization heuristic with a uniform grid. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
    [details] [full text] [poster] [slides]
    BibTeX
    @inproceedings{giscup-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus V. A.",
    title = "Fast map generalization heuristic with a uniform grid",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    address = "Dallas, Texas, USA",
    href = "\bibhrefptp{185-acmgis2014-cup}{185-acmgis2014-cup-talk.ppt}{185-acmgis2014-cup-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/185-acmgis2014-cup-poster.pdf",
    customlinkslides = "https://wrfranklin.org/p/185-acmgis2014-cup-talk.ppt",
    mykey = "wenlili marcus salles gridgen"
}
  • Guilherme Pena, Salles de Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li, and Daniel Benedetti. An efficient GPU multiple-observer siting method based on sparse-matrix multiplication. In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014. Dallas TX USA, 4 Nov 2014.
    [details] [full text] [slides]
    Abstract
    This paper proposes an efficient parallel heuristic for siting observers on raster terrains. More specifically, the goal is to choose the smallest set of points on a terrain such that observers located in these points are able to visualize at least a given percentage of the terrain. This problem is NP-Hard and has several applications such as determining the best places to position (site) communication or monitoring towers on a terrain. Since siting observers is a massive operation, its solution requires a huge amount of processing time even to obtain an approximate solution using a heuristic. This is still more evident when processing high resolution terrains that have become available due to modern data acquiring technologies such as LIDAR and IFSAR. Our new implementation uses dynamic programming and CUDA to accelerate the swap local search heuristic, which was proposed in previous works. Also, to efficiently use the parallel computing resources of GPUs, we adapted some techniques previously developed for sparse-dense matrix multiplication. We compared this new method with previous parallel implementations and the new method is much more efficient than the previous ones. It can process much larger terrains (the older methods are restrictive about terrain size) and it is faster.
    BibTeX
    @inproceedings{bigspatial-2014,
    author = "Pena, Guilherme and de Magalhães, Salles and Andrade, Marcus and Franklin, Randolph and Ferreira, Chaulio and Li, Wenli and Benedetti, Daniel",
    title = "An efficient {GPU} multiple-observer siting method based on sparse-matrix multiplication",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014",
    year = "2014",
    month = "4 Nov",
    address = "Dallas TX USA",
    href = "\bibhrefpt{191-bigspatial-sparse-siting-2014}{191-bigspatial-sparse-siting-2014-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/191-bigspatial-sparse-siting-2014-talk.pdf",
    mykey = "visviewshedsiting benedetti marcus wenlili salles parallel"
}
  • Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient map generalization heuristic based on the Visvalingam–Whyatt algorithm. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
    [details] [full text] [slides]
    BibTeX
    @inproceedings{salles-fwcg-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient map generalization heuristic based on the {V}isvalingam--{Whyatt} algorithm",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles",
    customlinkslides = "https://wrfranklin.org/p/188-fwcg2014-salles-mapgen-talk.pdf",
    href = "\bibhrefpt{188-fwcg2014-salles-mapgen}{188-fwcg2014-salles-mapgen-talk.pdf}"
}
  • Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Restricted bathymetric tracklines interpolation. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
    [details] [full text] [slides]
    Abstract
    In this paper, we propose a method to interpolate a small bathymetry with long and thin sand bars as distinctive features. Underwater terrain, or bathymetry, is measured by a single beam or multibeam echosounder attached under a boat. Measurement points are distributed along the a track of the boat and their positions and values constitute a trackline. Although full coverage is possible in multibeam surveys, tracklines are often sparse and thin, especially in single beam surveys, and it is expected to interpolate the bathymetry from tracklines. There are dozens of existing spatial interpolation methods with their strengths and weaknesses, and some are more widely used than others. One of the methods, overdetermined laplacian partial differentiation equations (ODETLAP), has been successfully used in bathymetry data interpolation and shown to be better than some of the popular methods. However, it is more suited for large-scale bathymetry without significant linear or continuous features.
    BibTeX
    @inproceedings{li-fwcg-2014,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Restricted Bathymetric Tracklines Interpolation",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "marcus wenlili salles bathy",
    customlinkslides = "https://wrfranklin.org/p/187-fwcg2014-li-bathy-talk.pdf",
    href = "\bibhrefpt{187-fwcg2014-li-bathy}{187-fwcg2014-li-bathy-talk.pdf}"
}
  • Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel algorithm for viewshed computation on grid terrains. Journal of information and data management, 2014. invited.
    [details] [full text]
    Abstract
    Viewshed (or visibility map) computation is an important component in many GIScience applications and, as nowadays there are huge volume of terrain data available at high resolutions, it is important to develop efficient algorithms to process these data. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. In this paper, we describe a new parallel algorithm based on the model proposed by Van Kreveld. Our algorithm uses the shared memory model, which is relatively cheap and supported by most current processors. Experiments have shown that, with 16 parallel cores,was up to 12 times faster than the serial implementation, and up to 3.9 times using four parallel cores, which isalmost optimal speedup.
    BibTeX
    @article{chaulio-jidm-2014,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A parallel algorithm for viewshed computation on grid terrains",
    journal = "Journal of information and data management",
    year = "2014",
    volume = "5",
    number = "1",
    note = "invited",
    href = "\bibhref{180-jidm2014-chaulio-parallel-viewshed}",
    mykey = "visviewshedsiting marcus salles parallel"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A linear time algorithm to compute the drainage network on grid terrains. J. Hydroinformatics, 16(6):1227–1234, 2014. Update of the winner of the Best Paper Award (2nd place) at AGILE 2012. doi:https://doi.org/10.2166/hydro.2013.068.
    [details] [full text]
    BibTeX
    @article{salles-hydroinformatics-2014,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "A linear time algorithm to compute the drainage network on grid terrains",
    journal = "J. Hydroinformatics",
    year = "2014",
    volume = "16",
    number = "6",
    pages = "1227--1234",
    href = "\bibhref{166-hydroinformatics-maghalaes-rwflood}",
    doi = "https://doi.org/10.2166/hydro.2013.068",
    note = "Update of the winner of the Best Paper Award (2nd place) at AGILE 2012",
    mykey = "marcus salles rwflood hydro sallesagile2012"
}
  • Guilherme C. Pena, Marcus V.A. Andrade, Salles V.G. de Magalhães, W. R. Franklin, and Chaulio R. Ferreira. An improved parallel algorithm using GPU for siting observers on terrain. In 16th International Conference on Enterprise Information Systems (ICEIS 2014), 367–375. Lisbon, 27–30 April 2014. doi:https://doi.org/10.5220/0004884303670375.
    [details] [full text] [slides]
    Abstract
    This paper presents an efficient method to determine a set of observers (that is, where to site them) such that a given percentage of a terrain is visually covered. Our method extends the method proposed in (Franklin, 2002) including a local search heuristic efficiently implemented using dynamic programming and GPU parallel programming. This local search strategy allows to achieve a higher coverage using the same number of observers as the original method and thus it is possible to obtain a given coverage using a smaller number of observers. It can be an important improvement since an observer can represent an expensive facility such as a telecommunication tower. The proposed method performance was compared with that of other methods and the tests showed that it can be more than 1200 times faster than the sequential implementation (with no use of dynamic programming and no GPU parallel programmming) and, also, more than 20 times faster than a previous parallel method presented in (de Magalhaes et al., 2011).
    BibTeX
    @inproceedings{iceis-2014,
    author = "Pena, Guilherme C. and Andrade, Marcus V.A. and de Magalhães, Salles V.G. and Franklin, W. R. and Ferreira, Chaulio R.",
    title = "An Improved Parallel Algorithm using {GPU} for Siting Observers on Terrain",
    booktitle = "16th International Conference on Enterprise Information Systems ({ICEIS} 2014)",
    year = "2014",
    month = "27--30 April",
    address = "Lisbon",
    pages = "367--375",
    doi = "https://doi.org/10.5220/0004884303670375",
    href = "\bibhrefpt{177-ICEIS2014-pena-site-gpu}{177-ICEIS2014-pena-site-gpu-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/177-ICEIS2014-pena-site-gpu-talk.pdf",
    mykey = "visviewshedsiting gpusiting marcus salles parallel"
}

2013

  • Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel sweep line algorithm for visibility computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013. Winner of best paper award, \url http://www.geoinfo.info/geoinfo2013/index.php.
    [details] [full text]
    Abstract
    This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.
    BibTeX
    @inproceedings{chaulio-geoinfo-2013,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A Parallel Sweep Line Algorithm for Visibility Computation",
    booktitle = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
    year = "2013",
    month = "24--27 Nov",
    address = "Campos do Jordão, SP, Brazil",
    href = "\bibhref{174-geoinfo2013-chaulio-sweep}",
    note = "Winner of best paper award, \url{http://www.geoinfo.info/geoinfo2013/index.php}",
    mykey = "marcus salles visviewshedsiting parallel chauliogeoinfo2013"
}

2012

  • Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Computing the drainage network on huge grid terrains. In 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial-2012). Redondo Beach, CA, 6 Nov 2012.
    [details] [full text] [slides]
    BibTeX
    @inproceedings{gomes-acmgis-2012,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Computing the drainage network on huge grid terrains",
    address = "Redondo Beach, CA",
    month = "6 Nov",
    customlinkslides = "https://wrfranklin.org/p/162-bigspatial2012-drainage-talk.pdf",
    href = "\bibhrefpt{162-bigspatial2012-drainage}{162-bigspatial2012-drainage-talk.pdf}",
    booktitle = "1st {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data {(BigSpatial-2012)}",
    mykey = "marcus salles hydro emflow",
    year = "2012"
}
  • Chaulio R. Ferreira, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and André M. Pompermayer. More efficient terrain viewshed computation on massive datasets using external memory. In 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012). Redondo Beach, CA, 6–9 Nov 2012.
    [details] [full text] [poster]
    Abstract
    We present a better algorithm and implementation for external memory viewshed computation. It is about four times faster than the most recent and most efficient published methods. Ours is also much simpler. Since processing large datasets can take hours, this improvement is significant. To reduce the total number of I/O operations, our method is based on subdividing the terrain into blocks which are stored in a special data structure managed as a cache memory. The viewshed is that region of the terrain that is visible by a fixed observer, who may be on or above the terrain. Its applications range from visual nuisance abatement to radio transmitter siting and surveillance.
    BibTeX
    @inproceedings{ferreira-acmgis-2012,
    author = "Ferreira, Chaulio R. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pompermayer, André M.",
    title = "More efficient terrain viewshed computation on massive datasets using external memory",
    booktitle = "20th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2012)",
    year = "2012",
    address = "Redondo Beach, CA",
    month = "6--9 Nov",
    href = "\bibhrefpp{159-acmgis2012-viewshed}{159-acmgis2012-viewshed-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/159-acmgis2012-viewshed-poster.pdf",
    mykey = "visviewshedsiting marcus salles"
}
  • Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain. In Jérome Gensel, Didier Josselin, and Danny Vandenbroucke, editors, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391–407. Springer, Avignon (France), 24–27 April 2012. URL: http://agile2012.imag.fr/.
    [details] [full text] [slides]
    BibTeX
    @incollection{salles-agile-2012,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny",
    title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain",
    booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference",
    publisher = "Springer",
    pages = "391--407",
    isbn = "978-3-642-29062-6",
    year = "2012",
    address = "Avignon (France)",
    month = "24--27 April",
    note = "Winner of the Best Paper Award (2nd place)",
    url = "http://agile2012.imag.fr/",
    customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf",
    href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}",
    mykey = "salles marcus hydro rwflood sallesagile2012"
}

2011

  • Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management (IJCISIM), 2011.
    [details] [full text]
    Abstract
    This paper presents an heuristic method to give an approximated solution to the observer siting problem on high resolution terrains that are too large to be processed in the internal memory. Informally, the problem is to determine an optimal positioning of as few as possible observers for being able to observe as many target points as possible. Tests have shown that the proposed heuristic can solve this problem using, on average, fifteen percent fewer observers than another heuristic described in the literature. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems.
    BibTeX
    @article{magalhaes-ijcisim-2011,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "Multiple Observer Siting in Huge Terrains Stored in External Memory",
    journal = "International Journal of Computer Information Systems and Industrial Management (IJCISIM)",
    year = "2011",
    volume = "3",
    issn = "2150-7988",
    href = "\bibhref{148-ijcisim11-emsite-magalhaes}",
    mykey = "visviewshedsiting marcus salles"
}

2010

  • Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. An optimization heuristic for siting observers in huge terrains stored in external memory. In 10th International Conference on Hybrid Intelligent Systems (HIS 2010). Atlanta USA, 23–25 Aug 2010.
    [details] [full text]
    BibTeX
    @inproceedings{magalhaes-his-2010,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "An optimization heuristic for siting observers in huge terrains stored in external memory",
    booktitle = "10th International Conference on Hybrid Intelligent Systems ({HIS} 2010)",
    address = "Atlanta USA",
    month = "23--25 Aug",
    year = "2010",
    href = "\bibhref{132-atlanta-his10-emsite-magalhaes}",
    mykey = "marcus salles"
}
  • Marcus V. A. Andrade, Salles V. G. de Magalhães, Mirella A. de Magalhães, W. Randolph Franklin, and Barbara M. Cutler. Efficient viewshed computation on terrain in external memory. Geoinformatica, 2010. (online 26 Nov 2009). URL: http://www.springerlink.com/content/p1783648185g1252/, doi:https://doi.org/10.1007/s10707-009-0100-9.
    [details] [full text]
    Abstract
    The recent availability of detailed geographic data permits terrain applications to process large areas at high resolution. However the required massive data processing presents significant challenges, demanding algorithms optimized for bothdata movement and computation. One such application is viewshed computation,that is, to determine all the points visible from a given point p. In this paper, we present an efficient algorithm to compute viewsheds on terrain stored in external memory. In the usual case where the observer's radius of interest is smaller than the terrain size, the algorithm complexity is θ(scan(n2)) where n2 is the number of points in an n×n DEM and scan(n2)is the minimum number of I/O operations required to read n2 contiguous items from external memory. This is much faster than existing published algorithms.
    BibTeX
    @article{andrade-geoinfo-ext-viewshed-2008,
    author = "Andrade, Marcus V. A. and de Magalhães, Salles V. G. and de Magalhães, Mirella A. and Franklin, W. Randolph and Cutler, Barbara M.",
    title = "Efficient viewshed computation on terrain in external memory",
    journal = "Geoinformatica",
    year = "2010",
    href = "\bibhref{126-andrade-geoinfo-ext-viewshed-2008}",
    URL = "http://www.springerlink.com/content/p1783648185g1252/",
    DOI = "https://doi.org/10.1007/s10707-009-0100-9",
    mykey = "visviewshedsiting marcus salles",
    note = "(online 26 Nov 2009)"
}

2008

  • Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade. Parallel ODETLAP for terrain compression and reconstruction. In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008. URL: http://acmgis08.cs.umn.edu/.
    [details] [full text] [slides] [poster]
    Abstract
    We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors.
    BibTeX
    @inproceedings{stookey-acmgis-2008,
    author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.",
    editor = "Aref, Walid G.",
    title = "Parallel {ODETLAP} for terrain compression and reconstruction",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    location = "Irvine CA",
    month = "5--7 Nov",
    href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}",
    url = "http://acmgis08.cs.umn.edu/",
    customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf",
    customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt",
    mykey = "odetlap tracy marcus xie stuetzle parallel"
}
  • Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Franklin T. Luk, Marcus Andrade, and Jared Stookey. Path planning on a compressed terrain. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
    [details] [full text] [slides] [poster]
    BibTeX
    @inproceedings{tracy-acmgis-2008,
    author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Luk, Franklin T. and Andrade, Marcus and Stookey, Jared",
    editor = "Aref, Walid G. and others",
    title = "Path Planning on a Compressed Terrain",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    address = "Irvine CA",
    month = "5--7 Nov",
    customlinkslides = "https://wrfranklin.org/p/124-acmgis2008-tracy-talk.pdf",
    customlinkposter = "https://wrfranklin.org/p/124-acmgis2008-tracy-poster.pdf",
    mykey = "pathplan marcus tracy",
    href = "\bibhrefpttpp{124-acmgis2008-tracy}",
    note = "(poster and fast forward presentation)",
    url = "http://acmgis08.cs.umn.edu/"
}
  • Christopher Stuetzle, W. Randolph Franklin, Barbara Cutler, Jonathan Muckell, Marcus Andrade, Jared Stookey, Metin Inanc, and Zhongyi Xie. Evaluating hydrology preservation of simplified terrain representations. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (PhD student poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
    [details] [slides] [poster]
    BibTeX
    @inproceedings{muckell-acmgis-2008,
    author = "Stuetzle, Christopher and Franklin, W. Randolph and Cutler, Barbara and Muckell, Jonathan and Andrade, Marcus and Stookey, Jared and Inanc, Metin and Xie, Zhongyi",
    editor = "Aref, Walid G. and others",
    title = "Evaluating Hydrology Preservation of Simplified Terrain Representations",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    address = "Irvine CA",
    month = "5--7 Nov",
    mykey = "inanc muckell marcus xie terrain hydro",
    customlinkslides = "https://wrfranklin.org/p/125-acmgis2008-muckell-talk.ppt",
    customlinkposter = "https://wrfranklin.org/p/125-acmgis2008-muckell-poster.ppt",
    href = "\bibhreftp{125-acmgis2008-muckell-talk.ppt}{125-acmgis2008-muckell-poster.ppt}",
    note = "(PhD student poster and fast forward presentation)",
    url = "http://acmgis08.cs.umn.edu/"
}
  • Daniel M. Tracy, W Randolph Franklin, Barb Cutler, Franklin Luk, Marcus Andrade, and Jared Stookey. Path planning on complex terrain. In 18th Fall Workshop on Computational Geometry (FWCG 2008). Rensselaer Polytechnic Institute, Troy NY USA, 31 Oct – 1 Nov 2008. (extended abstract, talk and poster).
    [details] [full text] [slides] [poster]
    BibTeX
    @inproceedings{tracy-fwcg-2008,
    author = "Tracy, Daniel M. and Franklin, W Randolph and Cutler, Barb and Luk, Franklin and Andrade, Marcus and Stookey, Jared",
    title = "Path Planning on Complex Terrain",
    booktitle = "18th Fall Workshop on Computational Geometry ({FWCG} 2008)",
    month = "31 Oct -- 1 Nov",
    year = "2008",
    note = "(extended abstract, talk and poster)",
    address = "Rensselaer Polytechnic Institute, Troy NY USA",
    customlinkslides = "https://wrfranklin.org/p/128-fwcg2008-tracy-talk.ppt",
    customlinkposter = "https://wrfranklin.org/p/128-fwcg2008-tracy-poster.ppt",
    mykey = "pathplan marcus tracy",
    href = "\bibhrefatp{128-fwcg2008-tracy}{128-fwcg2008-tracy-talk.ppt}{128-fwcg2008-tracy-poster.ppt}"
}
  • Zhongyi Xie, Marcus A. Andrade, W Randolph Franklin, Barbara Cutler, Metin Inanc, Jonathan Muckell, and Daniel M. Tracy. Progressive transmission of lossily compressed terrain. In CLEI 2008 Conferencia Latinoamericana de Informática. Santa Fe, Argentina, 8–12 Sep 2008.
    [details] [full text]
    BibTeX
    @inproceedings{andrade-prog-trans-2008,
    author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W Randolph and Cutler, Barbara and Inanc, Metin and Muckell, Jonathan and Tracy, Daniel M.",
    title = "Progressive Transmission of Lossily Compressed Terrain",
    booktitle = "{CLEI 2008} Conferencia Latinoamericana de Informática",
    year = "2008",
    address = "Santa Fe, Argentina",
    month = "8--12 Sep",
    href = "\bibhref{127-andrade-prog-trans-2008}",
    mykey = "marcus tracy inanc muckell xie terrain"
}
  • Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Hydrology-aware constrained triangulation of terrain data. (unpublished), Apr 2008.
    [details] [full text]
    BibTeX
    @unpublished{muckell-HydroTIN-2008,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Hydrology-Aware Constrained Triangulation of Terrain Data",
    mykey = "inanc marcus muckell xie tracy hydro",
    href = "\bibhref{120-muckell-HydroTIN-2008}",
    note = "(unpublished)",
    month = "Apr",
    year = "2008"
}
  • Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Evaluating hydrology preservation of simplified terrain representations. (unpublished), Apr 2008.
    [details] [full text]
    BibTeX
    @unpublished{muckell-HydroMetric-ODETLAP-2008,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Evaluating Hydrology Preservation of Simplified Terrain Representations",
    href = "\bibhref{121-muckell-HydroMetric-ODETLAP-2008}",
    note = "(unpublished)",
    month = "Apr",
    mykey = "odetlap tracy inanc marcus muckell xie hydro",
    year = "2008"
}
  • W. Randolph Franklin, Daniel M. Tracy, Marcus Andrade, Jonathan Muckell, Metin Inanc, Zhongyi Xie, and Barbara Cutler. Slope accuracy and path planning on compressed terrain. In Symposium on Spatial Data Handling. Montpellier FR, June 2008.
    [details] [full text]
    BibTeX
    @inproceedings{wrf-sdh-2008,
    author = "Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus and Muckell, Jonathan and Inanc, Metin and Xie, Zhongyi and Cutler, Barbara",
    title = "Slope Accuracy and Path Planning on Compressed Terrain",
    booktitle = "Symposium on Spatial Data Handling",
    year = "2008",
    month = "June",
    address = "Montpellier FR",
    mykey = "tracy inanc marcus muckell xie pathplan terrain",
    href = "\bibhref{119-sdh08-slope}"
}

2007

  • Zhongyi Xie, Marcus A. Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Daniel M. Tracy, and Jonathan Muckell. Approximating terrain with over-determined Laplacian PDEs. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. (poster session, no formal proceedings).
    [details] [full text] [poster]
    BibTeX
    @inproceedings{xie-fwcg-2007,
    author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Tracy, Daniel M. and Muckell, Jonathan",
    title = "Approximating terrain with over-determined {Laplacian} {PDEs}",
    booktitle = "17th Fall Workshop on Computational Geometry",
    month = "2--3 Nov",
    mykey = "tracy inanc marcus xie muckell odetlap",
    year = "2007",
    note = "(poster session, no formal proceedings)",
    address = "IBM TJ Watson Research Center, Hawthorne NY",
    customlinkposter = "https://wrfranklin.org/p/117-fwcg07-xie-poster.ppt",
    href = "\bibhrefap{117-fwcg07-xie-abs}{117-fwcg07-xie-poster.ppt}"
}
  • Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Drainage network and watershed reconstruction on simplified terrain. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. poster session, no formal proceedings.
    [details] [full text] [slides]
    BibTeX
    @inproceedings{muckell-fwcg-2007,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Drainage network and watershed reconstruction on simplified terrain",
    booktitle = "17th Fall Workshop on Computational Geometry",
    month = "2--3 Nov",
    year = "2007",
    note = "poster session, no formal proceedings",
    address = "IBM TJ Watson Research Center, Hawthorne NY",
    customlinkslides = "https://wrfranklin.org/p/116-fwcg07-muckell-poster.ppt",
    mykey = "tracy marcus inanc muckell xie hydro",
    href = "\bibhrefap{116-fwcg07-muckell-abs}{116-fwcg07-muckell-poster.ppt}"
}
  • W Randolph Franklin, Metin Inanc, Zhongyi Xie, Daniel M. Tracy, Barbara Cutler, Marcus V A Andrade, and Franklin Luk. Smugglers and border guards – the GeoStar project at RPI. In 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007). Seattle, WA, USA, Nov 2007.
    [details] [full text] [slides]
    Abstract
    We present the GeoStar project at RPI, which researches various terrain (i.e., elevation) representations and operations thereon. This work is motivated by the large amounts of hi-res data now available. The purpose of each representation is to lossily compress terrain while maintaining important properties. Our ODETLAP representation generalizes a Laplacian partial differential equation by using two inconsistent equations for each known point in the grid, as well as one equation for each unknown point. The surface is reconstructed from a carefully chosen small set of known points. Our second representation segments the terrain intoa set of regions, each of which is simply described. Our third representation has the most long term potential: scooping, which forms the terrain by emulating surface water erosion. Siting hundreds of observers, such as border guards, so that their viewsheds jointly cover the maximum terrain is our first operation. This process allows both observer and target to be above the local terrain, and the observer to have a finite radius of interest. Planning a path so that a smuggler may get from point A to point B while maximally avoiding the border guards is our second operation. The path metric includes path length, distance traveled uphill,and amount of time visible to a guard. The quality of our representations is determined, not only by their RMS elevation error, but by how accurately they support these operations.
    BibTeX
    @inproceedings{acmgis07,
    author = "Franklin, W Randolph and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M. and Cutler, Barbara and Andrade, Marcus V A and Luk, Franklin",
    title = "Smugglers and border guards -- the {GeoStar} project at {RPI}",
    booktitle = "15th {ACM} International Symposium on Advances in Geographic Information Systems {(ACM GIS 2007)}",
    year = "2007",
    address = "Seattle, WA, USA",
    month = "Nov",
    customlinkslides = "https://wrfranklin.org/p/115-seattle07-acmgis-smugglers-talk.ppt",
    mykey = "pathplan visviewshedsiting marcus tracy inanc xie",
    href = "\bibhrefpt{115-seattle07-acmgis-smugglers}{115-seattle07-acmgis-smugglers-talk.ppt}"
}
  • Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Franklin T Luk, Metin Inanc, and Zhongyi Xie. Multiple observer siting and path planning on lossily compressed terrain. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-16.
    [details] [full text]
    Abstract
    We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards.
    BibTeX
    @inproceedings{dt-wrf-spie-2007,
    author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Luk, Franklin T and Inanc, Metin and Xie, Zhongyi",
    title = "Multiple observer siting and path planning on lossily compressed terrain",
    booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
    year = "2007",
    month = "27 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "paper 6697-16",
    mykey = "inanc tracy marcus xie pathplan visviewshedsiting",
    href = "\bibhref{114-spie07-tracy}"
}
  • Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Metin Inanc, and Daniel M. Tracy. Surface compression using over-determined Laplacian approximation. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-15.
    [details] [full text]
    Abstract
    BibTeX
    @inproceedings{zx-wrf-spie-2007,
    author = "Xie, Zhongyi and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Inanc, Metin and Tracy, Daniel M.",
    title = "Surface compression using over-determined {Laplacian} approximation",
    booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
    year = "2007",
    month = "27 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "paper 6697-15",
    href = "\bibhref{113-spie07-xie}",
    mykey = "marcus inanc xie odetlap"
}
Explore all pages →Back to top ↑