Search for: All records

Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. We present an 𝑂((𝑚+𝑛)log(𝑚+𝑛)+𝜅log𝑚) time algorithm for the problem, where 𝜅 is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+𝑚)log(𝑚+𝑛)). In addition, we solve the problem in 𝑂((𝑚+𝑛)log(𝑚+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 

Atomic force microscopy (AFM) in conjunction with microfluidic delivery was utilized to produce three-dimensional (3D) lipid structures following a custom design. While AFM is well-known for its spatial precision in imaging and 2D nanolithography, the development of AFM-based nanotechnology into 3D nanoprinting requires overcoming the technical challenges of controlling material delivery and interlayer registry. This work demonstrates the concept of 3D nanoprinting of amphiphilic molecules such as 1-palmitoyl-2-oleoyl-sn-glycero-3-phosphocholine (POPC). Various formulations of POPC solutions were tested to achieve point, line, and layer-by-layer material delivery. The produced structures include nanometer-thick disks, long linear spherical caps, stacking grids, and organizational chiral architectures. The POPC molecules formed stacking bilayers in these constructions, as revealed by high-resolution structural characterizations. The 3D printing reached nanometer spatial precision over a range of 0.5 mm. The outcomes reveal the promising potential of our designed technology and methodology in the production of 3D structures from nanometer to continuum, opening opportunities in biomaterial sciences and engineering, such as in the production of 3D nanodevices, chiral nanosensors, and scaffolds for tissue engineering and regeneration.