Computing and analyzing decision boundaries from shortest path maps
Graphical abstract
Display Omitted
References
[1]
NASA’s EarthData, Open access to open science, 2023, URL https://www.earthdata.nasa.gov/.
[2]
NASA’s Worldview, Data visualization application, 2023, URL https://worldview.earthdata.nasa.gov/.
[3]
Liu L., Padilla L., Creem-Regehr S.H., House D.H., Visualizing uncertain tropical cyclone predictions using representative samples from ensembles of forecast tracks, IEEE Trans Vis Comput Graphics 25 (1) (2019) 882–891,.
[4]
Alemany S., Beltran J., Perez A., Ganzfried S., Predicting hurricane trajectories using a recurrent neural network, in: Proceedings of the thirty-third AAAI conference on artificial intelligence and thirty-first innovative applications of artificial intelligence conference and ninth AAAI symposium on educational advances in artificial intelligence, AAAI Press, ISBN 978-1-57735-809-1, 2019,.
[5]
Rim C.B., Om K.C., Ren G., Kim S.S., Kim H.C., Chol O.K., Establishment of a wildfire forecasting system based on coupled weather–Wildfire modeling, Appl Geogr (ISSN ) 90 (2018) 224–228,. URL https://www.sciencedirect.com/science/article/pii/S014362281730317X.
[6]
Matyas C., Villegas J., Srinivasan S., Cayhunto I., Thapa B., Pennington-Gray L., Cognitive and affective responses of florida tourists after exposure to hurricane warning messages, Nat Hazards 66 (2013) 97–116,.
[7]
Furukawa H., Wang Z., A route evaluation method considering the subjective evaluation on walkability, safety, and pleasantness by elderly pedestrians, in: Satapathy S.C., Raju K.S., Shyamala K., Krishna D.R., Favorskaya M.N. (Eds.), Advances in decision sciences, image processing, security and computer vision, Springer International Publishing, Cham, ISBN 978-3-030-24322-7, 2020, pp. 408–416.
[8]
Trinh T.T., Vu D.M., Kimura M., Point-of-conflict prediction for pedestrian path-planning, in: Proceedings of the 12th international conference on computer modeling and simulation, Association for Computing Machinery, New York, NY, USA, ISBN 9781450377034, 2020, pp. 88–92,.
[9]
Zhang L., Liu M., Wu X., AbouRizk S.M., Simulation-based route planning for pedestrian evacuation in metro stations: A case study, Autom Constr (ISSN ) 71 (2016) 430–442,. URL https://www.sciencedirect.com/science/article/pii/S0926580516301856.
[10]
Farias R., Kallmann M., Optimal path maps on the GPU, IEEE Trans Vis Comput Graphics 26 (9) (2020) 2863–2874,.
[11]
Berg M.d., Cheong O., Kreveld M.v., Overmars M., Computational geometry: Algorithms and applications, third ed., Springer-Verlag TELOS, Santa Clara, CA, USA, ISBN 3540779736, 2008.
[12]
Nilsson N.J., A mobius automation: An application of artificial intelligence techniques, in: Proceedings of the 1st international joint conference on artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1969, pp. 509–520.
[13]
Lee D.T., Preparata F.P., Euclidean shortest paths in the presence of rectilinear barriers, Networks 14 (1984) 393–410.
[14]
Welzl E., Constructing the visibility graph for n-line segments in o(n2) time, Inf Process Lett 20 (1985) 167–171.
[15]
Overmars M.H., Welzl E., New methods for computing visibility graphs, in: Proceedings of the fourth annual symposium on computational geometry, Association for Computing Machinery, New York, NY, USA, ISBN 0897912705, 1988, pp. 164–171,.
[16]
Storer J.A., Reif J.H., Shortest paths in the plane with polygonal obstacles, J ACM (ISSN ) 41 (5) (1994) 982–1012,.
[17]
Mitchell J.S.B., Mount D.M., Papadimitriou C.H., The discrete geodesic problem, SIAM J Comput 16 (4) (1987) 647–668,.
[18]
Xin S.Q., Wang G.J., Improving Chen and Han’s algorithm on the discrete geodesic problem, ACM Trans Graph (ISSN ) 28 (4) (2009),.
[19]
Chen J., Han Y., Shortest paths on a polyhedron, in: Proceedings of the sixth annual symposium on computational geometry, Association for Computing Machinery, New York, NY, USA, ISBN 0897913620, 1990, pp. 360–369,.
[20]
Mitchell J.S.B., Shortest paths among obstacles in the plane, in: Proceedings of the ninth annual symposium on computational geometry, Association for Computing Machinery, New York, NY, USA, ISBN 0897915828, 1993, pp. 308–317,.
[21]
Hershberger J., Suri S., An optimal algorithm for euclidean shortest paths in the plane, SIAM J Comput 28 (6) (1999) 2215–2256,.
[22]
Camporesi C., Kallmann M., Computing shortest path maps with GPU shaders, in: Proceedings of the seventh international conference on motion in games, Association for Computing Machinery, New York, NY, USA, ISBN 9781450326230, 2014, pp. 97–102,.
[23]
Farias R., Kallmann M., GPU-based max flow maps in the plane, in: Kress-Gazit H., Srinivasa S.S., Howard T., Atanasov N. (Eds.), Robotics: Science and systems XIV, 2018,. URL http://www.roboticsproceedings.org/rss14/p52.html.
[24]
Standalone interactive graphics toolkit (SIG), 2022, https://bitbucket.org/mkallmann/sig/wiki/Home. [Last Accessed 30 April 2022],.
[25]
Lorensen W.E., Cline H.E., Marching cubes: A high resolution 3D surface construction algorithm, in: Proceedings of the 14th annual conference on computer graphics and interactive techniques, Association for Computing Machinery, New York, NY, USA, ISBN 0897912276, 1987, pp. 163–169,.
[26]
Bergman L., Rogowitz B., Treinish L., A rule-based tool for assisting colormap selection, in: Proceedings visualization ’95, 1995, pp. 118–125,.
[27]
Forman R., Morse theory for cell complexes, Adv Math (ISSN ) 134 (1) (1998) 90–145,. URL https://www.sciencedirect.com/science/article/pii/S0001870897916509.
[28]
Mischaikow K., Nanda V., Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput Geom (ISSN ) 50 (2) (2013) 330–353,.
[29]
Hotz I., Masood T.B., Sadlo F., Tierny J., Topological methods in data analysis and visualization VI, Springer, 2021.
[30]
Heitel M., Lebiedz D., On analytical and topological properties of separatrices in 1-D holomorphic dynamical systems and complex-time Newton flows, 2019, arXiv: Dynamical Systems.
[31]
MacEachren A., Boscoe F., Haug D., Pickle L., Geographic visualization: designing manipulable maps for exploring temporally varying georeferenced statistics, in: Proceedings IEEE symposium on information visualization (Cat. No.98TB100258), 1998, pp. 87–94,.
[32]
Klimov D., Shahar Y., Taieb-Maimon M., Intelligent visualization and exploration of time-oriented data of multiple patients, Artif Intell Med (ISSN ) 49 (1) (2010) 11–31,.
[33]
Hochheiser H., Shneiderman B., Using interactive visualizations of WWW log data to characterize access patterns and inform site design, J Am Soc Inf Sci Technol (ISSN ) 52 (4) (2001) 331–343.
[34]
Sharma R., Tomson A., Lobato E., Kallmann M., Padilla L., Data Driven Multi-Hazard Risk Visualization, in: Byška J., Jänicke S. (Eds.), EuroVis 2020 - Posters, The Eurographics Association, ISBN 978-3-03868-105-2, 2020,.
[35]
Daassi C., Nigay L., Fauvet M.C., A taxonomy of temporal data visualization techniques, 2005.
[36]
Aigner W., Miksch S., Müller W., Schumann H., Tominski C., Visualizing time-oriented data-A systematic view, Comput Graph (ISSN ) 31 (3) (2007) 401–409,.
[37]
Silva S.D.S., Santos B.S., Madeira J.S., Using color in visualization: A survey, Comput Graph 35 (2011) 320–333.
[38]
Silva S., Madeira J., Santos B.S., There is more to color scales than meets the eye: A review on the use of color in visualization, in: 2007 11th international conference information visualization, 2007, pp. 943–950,.
[39]
Levkowitz H., Herman G., Color scales for image data, IEEE Comput Graph Appl 12 (1) (1992) 72–80,.
[40]
Heliövaara S., Kuusinen J.-M., Rinne T., Korhonen T., Ehtamo H., Pedestrian behavior and exit selection in evacuation of a corridor – An experimental study, Saf Sci (ISSN ) 50 (2) (2012) 221–227,. URL https://www.sciencedirect.com/science/article/pii/S0925753511001913.
[41]
Ng C.M., Chow W., A brief review on the time line concept in evacuation, Int J Archit Sci 7 (1) (2006) 1–13.
[42]
Abdelghany A., Abdelghany K., Mahmassani H.S., Al-Zahrani A., Dynamic simulation assignment model for pedestrian movements in crowded networks, Transp Res Rec 2316 (1) (2012) 95–105.
[43]
Abdelghany A., Abdelghany K., Mahmassani H., Alhalabi W., Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities, European J Oper Res 237 (3) (2014) 1105–1118.
[44]
Haghani M., Optimising crowd evacuations: Mathematical, architectural and behavioural approaches, Saf Sci (ISSN ) 128 (2020),. URL https://www.sciencedirect.com/science/article/pii/S0925753520301429.
[45]
Tavares R.M., Design for horizontal escape in buildings: The use of the relative distance between exits as an alternative approach to the maximum travel distance, Saf Sci (ISSN ) 48 (10) (2010) 1242–1247,. URL https://www.sciencedirect.com/science/article/pii/S0925753510000809.
[46]
Kurdi H.A., Al-Megren S., Althunyan R., Almulifi A., Effect of exit placement on evacuation plans, European J Oper Res (ISSN ) 269 (2) (2018) 749–759,. URL https://www.sciencedirect.com/science/article/pii/S0377221718300869.
[47]
Kurdi H., Almulifi A., Al-Megren S., Youcef-Toumi K., A balanced evacuation algorithm for facilities with multiple exits, European J Oper Res (ISSN ) 289 (1) (2021) 285–296,. URL https://www.sciencedirect.com/science/article/pii/S0377221720306238.
[48]
Gao H., Medjdoub B., Luo H., Zhong H., Zhong B., Sheng D., Building evacuation time optimization using constraint-based design approach, Sustain Cities Soc 52 (2020).
[49]
Tierny J., Favelier G., Levine J.A., Gueunet C., Michaux M., The topology ToolKit, IEEE Trans Vis Comput Graphics 24 (1) (2018) 832–842,.
Index Terms
- Computing and analyzing decision boundaries from shortest path maps
Index terms have been assigned to the content through auto-classification.
Recommendations
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Computing shortest path maps with GPU shaders
MIG '14: Proceedings of the 7th International Conference on Motion in GamesWe present in this paper a new GPU-based approach to compute Shortest Path Maps (SPMs) from a source point in a polygonal domain. Our method takes advantage of GPU polygon rasterization with shader programming. After encoding the SPM in the frame buffer,...
Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O ( n log 3/2 n ) time and O ( n log n ) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
The Author(s).
Publisher
Pergamon Press, Inc.
United States
Publication History
Published: 04 March 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Jan 2025