Dynamic Voronoi Diagram for Moving Disks.

Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon [0, t∞). The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in O(kF logn + kC n logn) time with O(n logn) preprocessing time and O(n + kF + kC) memory for n disk generators, kF edge flips, and kC disk collisions during the time horizon. Given an event history, the Voronoi diagram of an arbitrary moment can be constructed in O(k∗ + n) time where k∗ represents the number of events in [0, t∗). An example of the collision avoidance problem among moving disks is given by predicting future conjunctions among the disks using the proposed algorithm. Dynamic Voronoi diagrams will be very useful as a platform for the planning and management of the traffics of unmanned vehicles such as cars on street, vessels on surface, drones and airplanes in air, and satellites in geospace.

Heavy metal accumulation in and food safety of shark meat from Jeju island, Republic of Korea.

Shark meat is consumed as a food source worldwide, especially in Asian countries. However, since sharks are apex predators in the ocean food chain, they are prone to bioaccumulation of heavy metals. More than 100 million sharks are caught annually for human consumption, and the safety of shark meat cannot be overemphasized. Here, we examined heavy metal concentration in the muscle tissue of 6 shark species including 3 migratory species (Carcharhinus brachyurus, Carcharhinus obscurus, and Isurus oxyrinchus) and 3 local species (Triakis scyllium, Mustelus manazo, and Cephaloscyllium umbratile) from fish markets in Jeju Island, Republic of Korea. The concentrations of 11 heavy metals (Cr, Fe, Cu, Zn, As, Se, Cd, Sn, Sb, Pb, and Hg) and MeHg were analyzed. The result showed that the average concentrations of all metals, except for that of As, were below the regulatory maximum limits of many organizations, including the Codex standard. Hg and MeHg were significantly correlated with body length, body weight, and age, and the concentration of Hg was expected to exceed the limit in C. brachyurus with a body length or weight of over 130 cm or 25 kg, respectively. Our results indicate that shark meat can expose consumers to a high level of As and that copper sharks bigger than the predicted size should be avoided for excessive Hg. Considering these findings, a detailed guideline on consumption of meat of different shark species should be suggested based on further investigation.

BetaSCPWeb: side-chain prediction for protein structures using Voronoi diagrams and geometry prioritization.

Many applications, such as protein design, homology modeling, flexible docking, etc. require the prediction of a protein's optimal side-chain conformations from just its amino acid sequence and backbone structure. Side-chain prediction (SCP) is an NP-hard energy minimization problem. Here, we present BetaSCPWeb which efficiently computes a conformation close to optimal using a geometry-prioritization method based on the Voronoi diagram of spherical atoms. Its outputs are visual, textual and PDB file format. The web server is free and open to all users at http://voronoi.hanyang.ac.kr/betascpweb with no login requirement.

Optimal ligand descriptor for pocket recognition based on the Beta-shape.

Structure-based virtual screening is one of the most important and common computational methods for the identification of predicted hit at the beginning of drug discovery. Pocket recognition and definition is frequently a prerequisite of structure-based virtual screening, reducing the search space of the predicted protein-ligand complex. In this paper, we present an optimal ligand shape descriptor for a pocket recognition algorithm based on the beta-shape, which is a derivative structure of the Voronoi diagram of atoms. We investigate six candidates for a shape descriptor for a ligand using statistical analysis: the minimum enclosing sphere, three measures from the principal component analysis of atoms, the van der Waals volume, and the beta-shape volume. Among them, the van der Waals volume of a ligand is the optimal shape descriptor for pocket recognition and best tunes the pocket recognition algorithm based on the beta-shape for efficient virtual screening. The performance of the proposed algorithm is verified by a benchmark test.