The 2-center problem for a set $$\varvec{S}$$ of $$\varvec{n}$$ points in the plane asks for two congruent circular disks of the minimum radius $$\varvec{r}^{\varvec{*}}$$ , whose union covers all points of $$\varvec{S}$$ . In this paper, we present an $$\varvec{O(n \log n)}$$ time and $$\varvec{O(n)}$$ space algorithm for computing $$\varvec{r}^{\varvec{*}}$$ . Since the lower time bound on the planar 2-center problem is $$\varvec{\Omega (n \log n)}$$ , both time and space complexities of our algorithm are optimal. Our result improves upon the previously known $$\varvec{O(n \log }^{\varvec{2}} \varvec{n)}$$ time algorithm, and solves a long-standing (near thirty years) open problem in computational geometry. It also contains $$\varvec{O(n \log n)}$$ time and $$\varvec{O(n)}$$ space algorithms for two other variants of the planar 2-center problem: The first is to cover a set of points in convex position, and the second is to cover a convex polygon $$\varvec{P}$$ , whose goal is to find two centers inside $$\varvec{P}$$ such that the maximum distance from any point of polygon $$\varvec{P}$$ to its closest center is minimized. Except for efficiency of our algorithms, the other novelty is their simplicity: Our algorithms are built on the standard ones for computing the Delaunay triangulation and furthest-site Voronoi diagram of a point set, which are easy to implement. In comparison to most existing 2-center algorithms, no parametric searches are needed.

A cluster is a set of points, with a predefined similarity measure. In this paper, we study the problem of computing the largest possible convex hulls, measured by length and by area, of the points that are selected from a set of convex-hull disjoint clusters, one per cluster. We show that the largest convex hulls for convex-hull disjoint clusters with bounded size , measured by length or area, can be computed in O ( n 4 ) time, where n is the number of given clusters. Our solution of either problem for arbitrarily given points relies on the convex hull of all points. Moreover, for a set of the clusters, whose all points are in convex position, its solution can be reduced to several instances of the problem of computing the single-source shortest-paths in a weighted graph. Not only our results significantly improve upon the known time bound O ( n 9 ) , but also the obtained solutions are unified and simple. Moreover, our algorithms can be used to improve the known results on several other variants of the considered problem.

Despite the success of recent upsampling approaches, generating high-resolution point sets with uniform distribution and meticulous structures is still challenging. Unlike existing methods that only take spatial information of the raw data into account, we regard point cloud upsampling as generating dense point clouds from deformable topology. Motivated by this, we present SPU-PMD, a self-supervised topological mesh deformation network, for 3D densification. As a cascaded framework, our architecture is formu-lated by a series of coarse mesh interpolator and mesh de-formers. At each stage, the mesh interpolator first produces the initial dense point clouds via mesh interpolation, which allows the model to perceive the primitive topology better. Meanwhile, the deformer infers the morphing by estimating the movements of mesh nodes and reconstructs the de-scriptive topology structure. By associating mesh deformation with feature expansion, this module progressively re-fines point clouds' surface uniformity and structural details. To demonstrate the effectiveness of the proposed method, extensive quantitative and qualitative experiments are con-ducted on synthetic and real-scanned 3D data. Also, we compare it with state-of-the-art techniques to further illus-trate the superiority of our network. The project page is: https://github.com/lyz21/spU-PMd.

This paper studies a searching problem in an unknown street. A simple polygon [Formula: see text] with two distinguished vertices, [Formula: see text] and [Formula: see text], is called a street if the two boundary chains from [Formula: see text] to [Formula: see text] are mutually weakly visible. We use a mobile robot to locate [Formula: see text] starting from [Formula: see text]. Assume that the robot has a limited sensing capability that can only detect the constructed edges (also called gaps) on the boundary of its visible region, but cannot measure any angle or distance. The robot does not have knowledge of the street in advance. We present a new competitive strategy for this problem and prove that the length of the path generated by the robot is at most 9-times longer than the shortest path. We also propose a matching lower bound to show that our strategy is optimal. Compared with the previous strategy, we further relaxed the restriction that the robot should take a marking device and use the data structure S-GNT. The analysis of our strategy is tight.

We consider the problem of evacuating some people from an unknown convex region. The people do neither have information about the region boundary nor their positions. We seek competitive strategy that achieves a competitive ratio of the evacuation path over the shortest path. In the scenario of general plane, we propose a strategy SOP for one group, and prove that its competitive ratio is 19.64. And we propose a 14.37-competitive strategy STP for two groups. Also, we present efficient strategies in the scenario of grid network. Furthermore, our strategies can be used for guiding the robot to search the boundary of an unknown region.

Channel routing is an important, time-consuming, and difficult problem in VLSI layout design, In this paper, we consider the two-terminal channel routing problem in the new routing model, called times square model (TSM); see, Lodj, Info. Proc. Lett., vol. 35, p. 41, 1990.; where the grid is composed of horizontal tracks, right tracks (with slope +60/spl deg/) and left tracks (with slope -60/spl deg/). We show a new lower bound [2d/3]-1 to the width of channel and present an optimal algorithm for two-terminal channel routing problems, which obtains [2d/3]+2 as an upper bound to the channel width where d is the channel density. The algorithm not only utilizes the horizontal tracks, but also the zig-zag connections, thus achieving the routing optimality.>