36 research outputs found
Visualizing WSPDs and Their Applications (Media Exposition)
No full textIntroduced by Callahan and Kosaraju back in 1995, the concept of well-separated pair decomposition (WSPD) has occupied a special significance in computational geometry when it comes to solving distance problems in d-space. We present an in-browser tool that can be used to visualize WSPDs and several of their applications in 2-space. Apart from research, it can also be used by instructors for introducing WSPDs in a classroom setting. The tool will be permanently maintained by the third author at https://wisno33.github.io/VisualizingWSPDsAndTheirApplications/
Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs
No full textWhen constructing geometric graphs (vertices are points and edges are line segments connecting point pairs) on pointsets, stretch-factor (worst-case detour between any point pair) is often considered a quality metric. A low stretch-factor (a quantity that is usually \u3e 1) guarantees short paths between all vertex pairs. A geometric graph having a stretch-factor of t is known as a t-spanner. Creating low stretch-factor geometric graphs for large pointsets with a low number of edges is an open problem in computational geometry.
In this work, we have designed and engineered a new simple and practical (fast and memory-efficient) algorithm named Fast-Sparse-Spanner algorithm for constructing sparse low stretch-factor geometric graphs on large pointsets in the plane. To the best of current knowledge, this is the first practical algorithm capable of constructing fast low stretch-factor graphs on large pointsets with averagedegrees (hence, the number of edges) competitive with that of greedy-spanners, the sparsest known class of Euclidean geometric spanners.
To evaluate the implementation in terms of computation speed, memory usage, and quality of output, extensive experiments were performed with synthetic and real-world pointsets, comparing results to Bucketing, the fastest known greedy spanner algorithm for pointsets in the plane, devised by Alewijnse et al. (Algorithmica, 2017). An experiment constructing a 1.1-spanner on a large synthetic pointset with 128K points uniformly distributed within a square demonstrated more than a 41-fold speedup, using roughly a third of the memory of Bucketing, with only a 3% increase in the average-degree of the resulting graph. When run on a pointset with a million points from the same distribution, a 130-fold speedup was observed, with roughly a fourth of the memory usage, and just a 6% increase in average-degree. In terms of diameter, the graphs generated by FastSparse-Spanner outperform greedy-spanners in most cases, exhibiting substantially lower diameter while maintaining near-greedy average-degree. Furthermore, the algorithm can be easily parallelized to take advantage of parallel environments.
As a byproduct of this research, Fast-Stretch-Factor was designed and engineered as a practical parallelizable algorithm to measure the stretch-factor of any graph generated by Fast-Sparse-Spanner. Experiments demonstrated that it is significantly faster than the naive Dijkstra-based stretch-factor measurement algorithm.
For broader uses and reproducibility of the results obtained, we have shared our code at https://github.com/ghoshanirban/FS
Optimal location of new forests in a suburban region
No full textThis paper looks at the optimal location of new forests in a suburban region under area constraints. The GIS-based methodology takes into account use benefits such as timber, hunting, carbon sequestration and recreation, non-use benefits (both bequest and existence values), opportunity costs of converting agricultural land, as well as planting and management costs of the new forest. The recreation benefits of new forest sites are estimated using function transfer techniques. We show that the net social benefit of the total afforestation project may vary up to a factor 6, depending on the forest sites that are selected. We show that the recreation value of a forest site varies considerably with the available substitutes.Benefit transfer, travel cost analysis, cost-benefit analysis, forest recreation, Geographical Information Systems (GIS)
Patentopia: A multi-stage patent extraction platform with disambiguation for certain semantic challenges
No full textBibliographic name disambiguation is an major semantic challenge, but critical to social sciences studies of important intellectual assets. Here we contribute to innovation research in several ways. We show a significant synonym problem in author names and discuss how a pre-processing heuristic step standardizing name variants helps, but homonyms generated with Chinese names are particularly difficult to resolve and manifest in an associated location list. Here we identify a new phenomenon of "onomastic profusion," the frequent use of certain words in firm names for semantic reasons that can confound disambiguation clustering algorithms. We illustrate these concerns with Patentopia, our customized platform accessing the PatentsView portal for the United States Patent and Trademark Office database and available for free academic use. This multi-stage system uses heuristics in concert with the PatentsView clustering process and reports meta-data to further assist analysis. As highly relevant use cases, we illustrate system performance with data derived from two important public innovation programs, I-Corps and Small Business Innovation Research (SBIR), and we close with implications for bibliometric analysis of current patent data.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Delft Centre for Entrepreneurshi
Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512
No full textsponsorship: This work was supported by the European Commission through the ICT programme under contract ICT-2007-216676 ECRYPT II and by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy). Parts of this work were carried out during the tenure of an ERCIM Alain Bensoussan Fellowship Programme and while authors were participating the ECRYPT2 workshop Hash3: Proofs, Analysis and Implementation in November 2009. The first author is supported by the Danish Council for Independent Research (FTP and FNU) grant 274-09-0096. (European Commission through the ICT programme|ICT-2007-216676 ECRYPT II, IAP Programme of the Belgian State (Belgian Science Policy)|P6/26 BCRYPT, ERCIM, Danish Council for Independent Research (FTP and FNU)|274-09-0096)status: Publishe
Assessing scientific research performance and impact with single indices
No full textWe provide a comprehensive and critical review of the h-index and its most important modifications proposed in the literature, as well as of other similar indicators measuring research output and impact. Extensions of some of these indices are presented and illustrated.Citation metrics, Research output, h-index, Hirsch index, h-type indices
Development of interpretable intelligent frameworks for estimating river water turbidity
No full textTurbidity (TU) is one of the paramount water quality indicators in rivers and streams. Therefore, knowledge of water TU plays a fundamental role in optimal managing and monitoring river water quality. This study aimed at developing four intelligent schemes including three boosting methods i.e. Categorical Boosting (CatBoost), Light Gradient-Boosting Machine (LightGBM), eXtreme Gradient Boosting (XGBoost), and a deep learning method named Convolutional Neural Networks (CNN). To evaluate the performance of proposed models, two gauging river stations situated in United States (i.e. USGS 14206950 and USGS 14211720) were selected as a case study. 70% and 30% of whole data were utilized as the training and validation datasets when developing the models, respectively. It is worthwhile to note that the development of boosting models and their performance companions with a deep learning model, as well as addressing the impacts of input features on the models’ outputs using SHapley Additive exPlanations (SHAP) are the novel aspects of this study, which have been rarely considered in preceding studies for river water TU estimation. Based on the achieved results during the validation period, the CatBoost and XGBoost models were found to be generally best models for an accurate estimation of river water TU in the studied sites. During the validation period, the best-performing models were XGBoost (R = 0.951, NSE = 0.903, RMSE = 3.552 FNU, MAE = 1.816 FNU) at USGS 14206950, and CatBoost (R = 0.961, NSE = 0.920, RMSE = 2.502 FNU, MAE = 1.219 FNU) at USGS 14211720 both established using full-input estimators. An interpretability assessment of the developed models was finally conducted taking into account the SHAP. Analysis of the SHAP graphs in a global level during the validation phase illustrated that river discharge was the most important input variable affecting the output results of the best-performing implemented models. © 2025 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group
Drivers of nitrogen and phosphorus dynamics in a groundwater-fed urban catchment revealed by high-frequency monitoring
No full textEutrophication of water bodies has been a problem causing severe degradation of water quality in cities. To gain mechanistic understanding of the temporal dynamics of nitrogen (N) and phosphorus (P) in a groundwater-fed lowlying urban polder, we applied high-frequency monitoring in Geuzenveld, a polder in the city of Amsterdam. The highfrequency monitoring equipment was installed at the pumping station where water leaves the polder. From March 2016 to June 2017, total phosphorus (TP), ammonium (NH4), turbidity, electrical conductivity (EC), and water temperature were measured at intervals of less than 20 min. This paper discusses the results at three timescales: Annual scale, rain event scale, and single pumping event scale. Mixing of upwelling groundwater (main source of N and P) and runoff from precipitation on pavements and roofs was the dominant hydrological process governing the temporal pattern of the EC, while N and P fluxes from the polder were also regulated by primary production and iron transformations. In our groundwater-seepage controlled catchment, NH4 appeared to be the dominant form of N with surface water concentrations in the range of 2-6 mgNL-1, which stems from production in an organic-rich subsurface. The concentrations of NH4 in the surface water were governed by the mixing process in autumn and winter and were reduced down to 0.1 mgNL-1 during the algal growing season in spring. The depletion of dissolved NH4 in spring suggests uptake by primary producers, consistent with high concentrations of chlorophyll a, O2, and suspended solids during this period. Total P and turbidity were high during winter (range 0.5-2.5 mg P L-1 and 200-1800 FNU, respectively, where FNU represents Formazin Nephelometric Unit) due to the release of P and reduced iron from anoxic sediment to the water column, where Fe2C was rapidly oxidized and precipitated as iron oxides which contributed to turbidity. In the other seasons, P is retained in the sediment by sorption to precipitated iron oxides. Nitrogen is exported from the polder to the receiving waters throughout the whole year, mostly in the form of NH4 but in the form of organic N in spring. P leaves the polder mainly during winter, primarily associated with Fe(OH)3 colloids and as dissolved P. Based on this new understanding of the dynamics of N and P in this low-lying urban catchment, we suggested management strategies that may effectively control and reduce eutrophication in urban polders and receiving downstream waters. Sanitary Engineerin
A Logical Relation for Monadic Encapsulation of State: Proving contextual equivalences in the presence of runST
No full textWe present a logical relations model of a higher-order functional programming language with impredicative polymorphism, recursive types, and a Haskell-style ST monad type with runST. We use our logical relations model to show that runST provides proper encapsulation of state, by showing that e effectful computations encapsulated by runST are heap independent. Furthermore, we show that contextual refinements and equivalences that are expected to hold for pure computations do indeed hold in the presence of runST. This is the first time such relational results have been proven for a language with monadic encapsulation of state. We have formalized all the technical development and results in Coq.sponsorship: The last author would like to thank Georg Neis for early discussions about the topic of this paper. We would like to thank the anonymous referees for their invaluable constructive comments. This research was supported in part by the ModuRes Sapere Aude Advanced Grant from The Danish Council for Independent Research for the Natural Sciences (FNU), by the EUTypes funding ECOST-STSM-CA15123-150816-080859 and by the Flemish Research Fund grants G.0058.13 (until June 2017) and G.0962.17N (since July 2017). (Danish Council for Independent Research for the Natural Sciences (FNU), EUTypes|ECOST-STSM-CA15123-150816-080859, Flemish Research Fund|G.0058.13, Flemish Research Fund|G.0962.17N)status: Publishe
Optimizing Antibiotic Duration for Spontaneous Bacterial Peritonitis Prophylaxis: Time to Rethink
No full textAbstract are not provided by the author/publisher
