Proposed projects for CMSC 725 in Spring 2022 1. Use well-separated pairs (wsp) on traveling salesman problem and other problems. Jerry Qian tried it in 2021 but did not complete it. Jagan Sankarayanan will work with you on it and will try to get access to Jerry'code and project report (geometric solution). In particular, similar to SILC and PCP, one could also look into the role of geometry in the traveling salesman problem (TSP). It is unlikely that the geometrical approach would yield a polynomial solution for TSP, but the goal is to explore a few interesting "geometrical" insights into the TSP problem. We will use well-separated pairs (WSP) as the primary data structure here. Given a set of points that is embedded in an Euclidean space, can we pose the following problem: a. Is there a quick test to say that the given configuration of points has an optimal polynomial time solution? If so, can we find it. b. Can WSP be used to find an approximate solution in polynomial time? yet we can provide linear bounds to the optimal solution? In other words, can we say that the approximate solution is 10, but the optimal solution is 10x, where x is some factor of the separation factor? c. If we can constrain the points to be in integer locations and the map size is bounded, does a polynomial time optimal solution exist? d. If one makes sufficient progress, then we could ask if we had the set of points and say a distance oracle, can we do the same problem on a road network? As one can see there are many variations to this problem that are mildly interesting (probably from a theoretical standpoint) but quite very powerfully from a practicality standpoint. One could make baby steps towards understanding the role of geometry in TSP. 2. WatchStand or NewsWatch - NewsStand on smartwatch (Apple or Android) 3. Incorporate Chronicling America database and UI iNewsStand 4. Incorporate text of videos into NewsStand clusters: two option: A. video is in the same cluster as the containing article B. video is in the cluster into which its text falls 5. Survey ride-sharing papers and look into implementing zoom lunch which differs from ride sharing in having multiple destinations. Key is to have the same delivery time rather than the same delivery location as in ride sharing. TO DO: A. find some more text on this problem. B. DOOR-DASH functioality 6. Modify web-baesd NewsStand not to open a new tab when looking at images which means that we cannot simply return to th invoking page with a "back" action, This requires you to really know what you are doing. 7. Reimplement VASCO in Python instead of Java 8. Reimplement the SAND Browser in Python instead of Java 9. Incorporate visibilty \glare of Sun into driving route planning. A. Google diections should minimize this in planning route B. Based on time of day C. Need a cost function that is elastic so that don't wait for sun to completely set or rise D. Can sell as a safety feature - Tesla E. How does the sun's glare affect the navigation, if any, of a self-driving car 10. WeatherStand which looks for weather-related terms in news articles like hurricane, tornado, etc. just as done for brands, diseases, people, crimes, keywords etc, A, Need an ontology of such words B. Create a temporal version which lets you track a particular hurricane, storm name 11. Create PRO-POWER which tracks power failure reports in a manner similar to diseases in PRO-MED, 12. CoronaViz enhancments (Harsh) A. Slochum comments like using geo-squares instead of geo-circles (ask Brian) B. Include necklases to simplify many overlapping geo-circles C. Other suggestion (ask Brian) 13. Cluster preservation in translators like Google, MSR, Yahoo? (Nicole Schneider) ===================== 15. INPATH and prepare for prposal - Yunheng Han A. Jagan India colleague has just completed it B. Check if can handle all of the queries in the NSF proposal C. More INPATH queries using SQL 16. IOANNA - incremental optimal approximate nearest neighbor algorithm Library in the spirit of ANN of Mount and Arya. https://www.cs.umd.edu/~mount/ANN/ Should be data structure independent Library 17. Windowseat: indicates what you are flying over and seems to have been done aready but we but cannot locate the apps. A. FlyoverCountry B. inflighto 18. Nerve interface for interaction with smartwatch 19. AIRWC or WC2GO A. Find online directory of public toilets like office buildings, gas stations, fast food locations, restaurats, bars b. Develop an app like Uber/LYFT to find nearest public toilet 20.. Google Maps for building interiors - look at floor plans regpisterd in city halls - automatic generation A. Incorporate in Google Directions B. Can better estimate delivery time by including distance from the elevator or building entrance. 21. Keep track of cliical trials for particular diseases that are relevant to COVID-19, Spatially-referenced. Similar to Ontuition for which we have no code. 22. Survey of toponym recognition ane resolution papers 23. Sun on house 16. marco vs MSR for spreasheet 17. ICCV ANN 8. Reverse Gogole Scholar that indicates the context in which a paper is cited 10. Spatiotemporal NewsStand 11. Spatial blockchain - Rongjian Lan 12. Translation evaluation based on clustering 13. Sydney Herald into NewsStand 14. Column coherence in spreadsheet work of Marco 15. Toponym resolution with experts for all ambiguous specifications 16. Improved CrimeStand 17. Application with Rob Patro of SASH to bioinformatics data 18. Synonym search for Lockheed-Martin yielding Boeing 19. Transcribing videos for NewsStand 20. Clustering comparison of word2vec and TF-IDF 21. Caching of map tiles in NewsStand 22. Disease outbreaks monitoring and compare with HealthMap 23. Prove duality relationship between AVD(3,0) for the sites of a Voronoi and PM2 quadtree for the edges of the Voronoi Diagram. 24. Location-based word-clooud generator. Look at a summarizer and word cloud generator as in http://csrankings.org/ for news articles written in English or Spanish. Apply the word-cloud geenrator in NewsStand so that when we click on a headline, article, or cluster, we generate a word cloud for it which pops up on the display. 25. Investigate an online clustering algorithm and compare with leader-follower of NewsStand; find a better one. 26. Evaluate NewsStand's ranking algorithm which takes size, velocity, and acceleration for determiing cluster