Source author record

Haitao Wang

Haitao Wang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Artificial Intelligence Computer Vision Databases cond-mat.mtrl-sci Information Retrieval Computation and Language cond-mat.mes-hall cond-mat.str-el Discrete Mathematics Robotics

Catalog footprint

What is connected

39works

12topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Anatomy Aware Cascade Network: Bridging Epistemic Uncertainty and Geometric Manifold for 3D Tooth Segmentation

Accurate three-dimensional (3D) tooth segmentation from Cone-Beam Computed Tomography (CBCT) is a prerequisite for digital dental workflows. However, achieving high-fidelity segmentation remains challenging due to adhesion artifacts in naturally occluded scans, which are caused by low contrast and indistinct inter-arch boundaries. To address these limitations, we propose the Anatomy Aware Cascade Network (AACNet), a coarse-to-fine framework designed to resolve boundary ambiguity while maintaining global structural consistency. Specifically, we introduce two mechanisms: the Ambiguity Gated Boundary Refiner (AGBR) and the Signed Distance Map guided Anatomical Attention (SDMAA). The AGBR employs an entropy based gating mechanism to perform targeted feature rectification in high uncertainty transition zones. Meanwhile, the SDMAA integrates implicit geometric constraints via signed distance map to enforce topological consistency, preventing the loss of spatial details associated with standard pooling. Experimental results on a dataset of 125 CBCT volumes demonstrate that AACNet achieves a Dice Similarity Coefficient of 90.17 \% and a 95\% Hausdorff Distance of 3.63 mm, significantly outperforming state-of-the-art methods. Furthermore, the model exhibits strong generalization on an external dataset with an HD95 of 2.19 mm, validating its reliability for downstream clinical applications such as surgical planning. Code for AACNet is available at https://github.com/shiliu0114/AACNet.

preprint2026arXiv

CoFlow: Coordinated Few-Step Flow for Offline Multi-Agent Decision Making

Generative models have emerged as a promising paradigm for offline multi-agent reinforcement learning (MARL), but existing approaches require many iterative sampling steps. Recent few-step acceleration methods either distill a joint teacher into independent students or apply averaged velocity fields independently to each agent. Unfortunately, these few-step approaches hurt inter-agent coordination. We show that the efficiency-coordination trade-off is not inherent: single-pass multi-agent generation can preserve coordination when the velocity field is natively joint-coupled. We propose Coordinated few-step Flow (CoFlow), an architecture that combines Coordinated Velocity Attention (CVA) with Adaptive Coordination Gating. A finite-difference consistency surrogate further replaces memory-prohibitive Jacobian-vector product backpropagation through the averaged velocity field with two stop-gradient forward passes. Across 60 configurations spanning MPE, MA-MuJoCo, and SMAC, CoFlow matches or surpasses Gaussian policies, value-based methods, transformer policies, diffusion models, and prior flow baselines on episodic return. Three independent coordination probes confirm that CoFlow's improvements arise from inter-agent coordination rather than per-agent capacity. A denoising-step sweep shows that single-pass inference suffices on every configuration. CoFlow reaches state-of-the-art coordination quality in 1-3 denoising steps under both centralized and decentralized execution. Project Page: https://guowei-zou.github.io/coflow/

preprint2026arXiv

Discrimination Is Generation: Unifying Ranking and Retrieval from a Tokenizer Perspective

Semantic IDs (SIDs) define the generation space of generative recommendation and directly determine its personalization ceiling. However, existing tokenizers are trained independently with retrieval objectives, leaving personalization signals fully decoupled from the SID construction process -- a fundamental gap that causes generative retrieval to persistently lag behind discriminative ranking. In this paper, we rethink the essence of SIDs: \emph{ranking seeks argmax in item space while retrieval seeks argmax in token space; both are the same problem solved at different granularities.} Based on this insight, we propose \DIG (\textbf{D}iscrimination \textbf{I}s \textbf{G}eneration), which embeds the tokenizer inside a discriminative ranking model for end-to-end training -- the ranker naturally becomes a retrieval model, yielding two models from a single training run. \DIG is organized around a \emph{feature assignment taxonomy}: item-intrinsic static features are encoded into SIDs, user-item cross features (u2i) implicitly drive codebook boundaries toward recommendation decision boundaries during training, and an MLP$_\mathrm{u2t}$ distillation module approximates u2i at the token level for inference. Experiments on three public benchmarks and two industrial datasets demonstrate that \DIG simultaneously improves ranking, retrieval, and unified retrieval-ranking quality.

preprint2026arXiv

DynamicPO: Dynamic Preference Optimization for Recommendation

In large language model (LLM)-based recommendation systems, direct preference optimization (DPO) effectively aligns recommendations with user preferences, requiring multi-negative objective functions to leverage abundant implicit-feedback negatives and sharpen preference boundaries. However, our empirical analyses reveal a counterintuitive phenomenon, preference optimization collapse, where increasing the number of negative samples can lead to performance degradation despite a continuously decreasing training loss. We further theoretically demonstrate that this collapse arises from gradient suppression, caused by the dominance of easily discriminable negatives over boundary-critical negatives that truly define user preference boundaries. As a result, boundary-relevant signals are under-optimized, weakening the model's decision boundary. Motivated by these observations, we propose DynamicPO (Dynamic Preference Optimization), a lightweight and plug-and-play framework comprising two adaptive mechanisms: Dynamic Boundary Negative Selection, which identifies and prioritizes informative negatives near the model's decision boundary, and Dual-Margin Dynamic beta Adjustment, which calibrates optimization strength per sample according to boundary ambiguity. Extensive experiments on three public datasets show that DynamicPO effectively prevents optimization collapse and improves recommendation accuracy on multi-negative preference optimization methods, with negligible computational overhead. Our code and datasets are available at https://github.com/xingyuHuxingyu/DynamicPO.

preprint2026arXiv

Med-DisSeg: Dispersion-Driven Representation Learning for Fine-Grained Medical Image Segmentation

Accurate medical image segmentation is fundamental to precision medicine, yet robust delineation remains challenging under heterogeneous appearances, ambiguous boundaries, and large anatomical variability. Similar intensity and texture patterns between targets and surrounding tissues often lead to blurred activations and unreliable separation. We attribute these failures to representation collapse during encoding and insufficient fine grained multi scale decoding. To address these issues, we propose Med DisSeg, a dispersion driven medical image segmentation framework that jointly improves representation learning and anatomical delineation. Med DisSeg combines a lightweight Dispersive Loss with adaptive attention for fine grained structure segmentation. The Dispersive Loss enlarges inter sample margins by treating in batch hidden representations as negative pairs, producing well dispersed and boundary aware embeddings with negligible overhead. Based on these enhanced representations, the encoder strengthens structure sensitive responses, while the decoder performs adaptive multi scale calibration to preserve complementary local texture and global shape information. Extensive experiments on five datasets spanning three imaging modalities demonstrate consistent state of the art performance. Moreover, Med DisSeg achieves competitive results on multi organ CT segmentation, supporting its robustness and cross task applicability.

preprint2026arXiv

SpectraFlow: Unifying Structural Pretraining and Frequency Adaptation for Medical Image Segmentation

Medical image segmentation remains challenging in low-data regimes, where scarce annotations often yield poor generalization and ambiguous boundaries with missing fine structures. Recent self-supervised pretraining has improved transferability, but it often exhibits a texture bias. In contrast, accurate segmentation is inherently geometry-aware and depends on both topological consistency and precise boundary preservation. To address this problem, we propose a two-stage framework that couples structure-aware encoder pretraining with boundary-oriented decoding. In Stage-1, we aim to learn structure-aware representations for downstream segmentation in low-data regimes. To this end, we propose Mixed-Domain MeanFlow Pretraining, which aligns images and binary masks in a shared latent space through latent transport regression, where masks act as conditional structural guidance rather than prediction targets, making the pretraining task-agnostic. To further improve training stability under scarce supervision, we incorporate a lightweight Dispersive Loss to prevent representation collapse. In Stage-2, we fine-tune the pretrained encoder with a lightweight decoder that combines Direct Attentional Fusion for adaptive cross-scale gating and Frequency-Directional Dynamic Convolution for high-frequency boundary refinement under appearance variation. Experiments on ISIC-2016, Kvasir-SEG, and GlaS demonstrate consistent gains over state-of-the-art methods, with improved robustness in low-data settings and sharper boundary delineation.

preprint2024arXiv

Algorithms for Computing Closest Points for Segments

Given a set $P$ of $n$ points and a set $S$ of $n$ segments in the plane, we consider the problem of computing for each segment of $S$ its closest point in $P$. The previously best algorithm solves the problem in $n^{4/3}2^{O(\log^*n)}$ time [Bespamyatnikh, 2003] and a lower bound (under a somewhat restricted model) $Ω(n^{4/3})$ has also been proved. In this paper, we present an $O(n^{4/3})$ time algorithm and thus solve the problem optimally (under the restricted model). In addition, we also present data structures for solving the online version of the problem, i.e., given a query segment (or a line as a special case), find its closest point in $P$. Our new results improve the previous work.

preprint2022arXiv

Autonomous Electric Vehicle Battery Disassembly Based on NeuroSymbolic Computing

The booming of electric vehicles demands efficient battery disassembly for recycling to be environment-friendly. Due to the unstructured environment and high uncertainties, battery disassembly is still primarily done by humans, probably assisted by robots. It is highly desirable to design autonomous solutions to improve work efficiency and lower human risks in high voltage and toxic environments. This paper proposes a novel framework of the NeuroSymbolic task and motion planning method to disassemble batteries in an unstructured environment using robots automatically. It enables robots to independently locate and disassemble battery bolts, with or without obstacles. This study not only provides a solution for intelligently disassembling electric vehicle batteries but also verifies its feasibility through a set of test results with the robot accomplishing the disassembly tasks in a complex and dynamic environment.

preprint2022arXiv

Computing the Minimum Bottleneck Moving Spanning Tree

Given a set $P$ of $n$ points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in $O(n^2)$ time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of $O(n^{4/3} \log^3 n)$ time.

preprint2022arXiv

Real-space Observation of Incommensurate Spin Density Wave and Coexisting Charge Density Wave on Cr(001) surface

In itinerant magnetic systems, a spin density wave (SDW) state can be induced by Fermi surface nesting and electron-electron interaction. It may intertwine with other orders such as charge density wave (CDW), while their relation is still yet to be understood. Here via spin-polarized scanning tunneling microscopy, we directly observed long-range spin modulation on Cr(001) surface, which corresponds to the well-known incommensurate SDW of bulk Cr. It displays 6.0 nm in-plane period and anti-phase behavior between adjacent (001) planes. Meanwhile, we simultaneously observed the coexisting CDW with half the period of SDW. Such SDW/CDW have highly correlated domain structures and are in-phase. Surprisingly, the CDW displays a contrast inversion around a density-of-states dip at -22 meV, indicating an anomalous CDW gap opened below EF. These observations support that the CDW is a secondary order driven by SDW. Our work is not only a real-space characterization of incommensurate SDW, but also provides insights on how SDW and CDW coexist.

preprint2022arXiv

Unit-Disk Range Searching and Applications

Given a set $P$ of $n$ points in the plane, we consider the problem of computing the number of points of $P$ in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching in the plane can be adapted to this problem. For example, by adapting Matoušek's results, we can build a data structure of $O(n)$ space so that each query can be answered in $O(\sqrt{n})$ time. Our techniques lead to improvements for several other classical problems, such as batched range searching, counting/reporting intersecting pairs of unit circles, distance selection, discrete 2-center, etc. For example, given a set of $n$ unit disks and a set of $n$ points in the plane, the batched range searching problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in $O(n^{4/3}\log n)$ time while our new algorithm runs in $O(n^{4/3})$ time.

preprint2021arXiv

A New Algorithm for Euclidean Shortest Paths in the Plane

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of $O(n\log n)$ time and $O(n\log n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri's algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(n\log n)$. In this paper, we present a new algorithm of $O(n+h\log h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $Ω(n+h\log h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(\log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path.

preprint2020arXiv

A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space

Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of $P$. Previously, the "continuous" version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our "discrete" version of the problem has not been studied before. We present a linear-time algorithm for the problem.

preprint2020arXiv

Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments

In this paper, we first consider the subpath convex hull query problem: Given a simple path $π$ of $n$ vertices, preprocess it so that the convex hull of any query subpath of $π$ can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90'] proposed a data structure of $O(n)$ space and $O(\log n\log\log n)$ query time; reducing the query time to $O(\log n)$ increases the space to $O(n\log\log n)$. We present an improved result that uses $O(n)$ space while achieving $O(\log n)$ query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in $O(\log n)$ time each. Our new result leads to improvements for several other problems. In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of $n$ (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of $O(n\log n)$ space that can answer each query in $(\sqrt{n}\log n)$ time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to $O(n)$. All these are classical problems that have been studied extensively. Previously data structures of $\widetilde{O}(\sqrt{n})$ query time (the notation $\widetilde{O}$ suppresses a polylogarithmic factor) were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.

preprint2020arXiv

On the Planar Two-Center Problem and Circular Hulls

Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA'97] gave a randomized algorithm of $O(n\log^2n)$ expected time and Chan [CGTA'99] presented a deterministic algorithm of $O(n\log^2 n\log^2\log n)$ time. In this paper, we propose an $O(n\log^2 n)$ time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(n\log n\log\log n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.

preprint2020arXiv

Overview of the CCKS 2019 Knowledge Graph Evaluation Track: Entity, Relation, Event and QA

Knowledge graph models world knowledge as concepts, entities, and the relationships between them, which has been widely used in many real-world tasks. CCKS 2019 held an evaluation track with 6 tasks and attracted more than 1,600 teams. In this paper, we give an overview of the knowledge graph evaluation tract at CCKS 2019. By reviewing the task definition, successful methods, useful resources, good strategies and research challenges associated with each task in CCKS 2019, this paper can provide a helpful reference for developing knowledge graph applications and conducting future knowledge graph researches.

preprint2016arXiv

$ε$-Kernel Coresets for Stochastic Points

With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms for geometric or combinatorial optimization problems over such data. In this paper, we initiate the study of constructing $ε$-kernel coresets for uncertain points. We consider uncertainty in the existential model where each point's location is fixed but only occurs with a certain probability, and the locational model where each point has a probability distribution describing its location. An $ε$-kernel coreset approximates the width of a point set in any direction. We consider approximating the expected width (an \expkernel), as well as the probability distribution on the width (an \probkernel) for any direction. We show that there exists a set of $O(1/ε^{(d-1)/2})$ deterministic points which approximate the expected width under the existential and locational models, and we provide efficient algorithms for constructing such coresets. We show, however, it is not always possible to find a subset of the original uncertain points which provides such an approximation. However, if the existential probability of each point is lower bounded by a constant, an exp-kernel\ (or an fpow-kernel) is still possible. We also construct an quant-kernel coreset in linear time. Finally, combining with known techniques, we show a few applications to approximating the extent of uncertain functions, maintaining extent measures for stochastic moving points and some shape fitting problems under uncertainty.

preprint2016arXiv

An Improved Algorithm for Diameter-Optimally Augmenting Paths in a Metric Space

Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in $O(n\log^3 n)$ time. In this paper, based on new observations and different algorithmic techniques, we present an $O(n\log n)$ time algorithm.

preprint2016arXiv

Computing the $L_1$ Geodesic Diameter and Center of a Polygonal Domain

For a polygonal domain with $h$ holes and a total of $n$ vertices, we present algorithms that compute the $L_1$ geodesic diameter in $O(n^2+h^4)$ time and the $L_1$ geodesic center in $O((n^4+n^2 h^4)α(n))$ time, respectively, where $α(\cdot)$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $O(n^{7.73})$ or $O(n^7(h+\log n))$ time, and compute the geodesic center in $O(n^{11}\log n)$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $L_1$ shortest paths in polygonal domains.

preprint2016arXiv

Dispersing Points on Intervals

We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle.

preprint2016arXiv

On the Geodesic Centers of Polygonal Domains

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain $\mathcal{P}$ with a total of $n$ vertices. We discover many interesting observations. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of $\mathcal{P}$ that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition of $\mathcal{P}$, which is known to be $O(n^{10})$. One key observation is a $π$-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in $O(n^{11}\log n)$ time. Previously, an algorithm of $O(n^{12+ε})$ time was known for this problem, for any $ε>0$.

preprint2015arXiv

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2 \log n)$ time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ time. We present an $O(n \log n)$ time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ time, improving the previously best $O(n^2)$ time solution.

preprint2015arXiv

An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains

We consider the problem of finding minimum-link rectilinear paths in rectilinear polygonal domains in the plane. A path or a polygon is rectilinear if all its edges are axis-parallel. Given a set $\mathcal{P}$ of $h$ pairwise-disjoint rectilinear polygonal obstacles with a total of $n$ vertices in the plane, a minimum-link rectilinear path between two points is a rectilinear path that avoids all obstacles with the minimum number of edges. In this paper, we present a new algorithm for finding minimum-link rectilinear paths among $\mathcal{P}$. After the plane is triangulated, with respect to any source point $s$, our algorithm builds an $O(n)$-size data structure in $O(n+h\log h)$ time, such that given any query point $t$, the number of edges of a minimum-link rectilinear path from $s$ to $t$ can be computed in $O(\log n)$ time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithm computes such a data structure in $O(n\log n)$ time.

preprint2015arXiv

Computing Shortest Paths among Curved Obstacles in the Plane

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this paper, we consider the problem version on curved obstacles, commonly modeled as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons). Each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of $h$ pairwise disjoint splinegons with a total of $n$ vertices, we compute a shortest s-to-t path avoiding the splinegons, in $O(n+h\log^{1+ε}h+k)$ time, where k is a parameter sensitive to the structures of the input splinegons and is upper-bounded by $O(h^2)$. In particular, when all splinegons are convex, $k$ is proportional to the number of common tangents in the free space (called "free common tangents") among the splinegons. We develop techniques for solving the problem on the general (non-convex) splinegon domain, which also improve several previous results. In particular, our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among $h$ pairwise disjoint convex splinegons with a total of $n$ vertices. Our algorithm runs in $O(n+h\log h+k)$ time and $O(n)$ space, where $k$ is the number of all free common tangents. Even for the special case where all splinegons are convex polygons, the previously best algorithm for this visibility problem takes $O(n+h^2\log n)$ time.

preprint2015arXiv

Computing the $L_1$ Geodesic Diameter and Center of a Simple Polygon in Linear Time

In this paper, we show that the $L_1$ geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric properties of the $L_1$ geodesic balls, that is, the metric balls with respect to the $L_1$ geodesic distance. More specifically, in this paper we show that any family of $L_1$ geodesic balls in any simple polygon has Helly number two, and the $L_1$ geodesic center consists of midpoints of shortest paths between diametral pairs. These properties are crucial for our linear-time algorithms, and do not hold for the Euclidean case.

preprint2015arXiv

Computing the Rectilinear Center of Uncertain Points in the Plane

In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set $P$ of $n$ (weighted) uncertain points in the plane and each uncertain point has $m$ possible locations each associated with a probability for the point appearing at that location. The goal is to find a point $q^*$ in the plane which minimizes the maximum expected rectilinear distance from $q^*$ to all uncertain points of $P$, and $q^*$ is called a rectilinear center. We present an algorithm that solves the problem in $O(mn)$ time. Since the input size of the problem is $Θ(mn)$, our algorithm is optimal.

preprint2015arXiv

Linear Time Approximation Schemes for Geometric Maximum Coverage

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b rectangles such that the sum of the weights of the points in P covered by these rectangles is maximized.For any fixed > 0, we present efficient approximation schemes that can find (1-ε)-approximation to the optimal solution.In particular, for m = 1, our algorithm runs in linear time O(n log( 1/ε)), improving over the previous result. For m > 1, we present an algorithm that runs in O(n/εlog(1/ε)+m(1/ε)^(O(min(sqrt(m),1/ε))) time.

preprint2015arXiv

Range Queries on Uncertain Data

Given a set $P$ of $n$ uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on $P$ to answer range queries of the following three types for any query interval $I$: (1) top-$1$ query: find the point in $P$ that lies in $I$ with the highest probability, (2) top-$k$ query: given any integer $k\leq n$ as part of the query, return the $k$ points in $P$ that lie in $I$ with the highest probabilities, and (3) threshold query: given any threshold $τ$ as part of the query, return all points of $P$ that lie in $I$ with probabilities at least $τ$. We present data structures for these range queries with linear or nearly linear space and efficient query time.

preprint2014arXiv

Efficient Algorithms for One-Dimensional k-Center Problems

We consider the problem of finding k centers for n weighted points on a real line. This (weighted) k-center problem was solved in O(n log n) time previously by using Cole's parametric search and other complicated approaches. In this paper, we present an easier O(n log n) time algorithm that avoids the parametric search, and in certain special cases our algorithm solves the problem in O(n) time. In addition, our techniques involve developing interesting data structures for processing queries that find a lowest point in the common intersection of a certain subset of half-planes. This subproblem is interesting in its own right and our solution for it may find other applications as well.

preprint2014arXiv

Minimizing the Aggregate Movements for Interval Coverage

We consider an interval coverage problem. Given $n$ intervals of the same length on a line $L$ and a line segment $B$ on $L$, we want to move the intervals along $L$ such that every point of $B$ is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in $O(n^2)$ time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an $O(n\log n)$ time algorithm. We also show an $Ω(n\log n)$ time lower bound for this problem, which implies the optimality of our algorithm.

preprint2014arXiv

On Top-$k$ Weighted SUM Aggregate Nearest and Farthest Neighbors in the $L_1$ Plane

In this paper, we study top-$k$ aggregate (or group) nearest neighbor queries using the weighted SUM operator under the $L_1$ metric in the plane. Given a set $P$ of $n$ points, for any query consisting of a set $Q$ of $m$ weighted points and an integer $k$, $ 1 \le k \le n$, the top-$k$ aggregate nearest neighbor query asks for the $k$ points of $P$ whose aggregate distances to $Q$ are the smallest, where the aggregate distance of each point $p$ of $P$ to $Q$ is the sum of the weighted distances from $p$ to all points of $Q$. We build an $O(n\log n\log\log n)$-size data structure in $O(n\log n \log\log n)$ time, such that each top-$k$ query can be answered in $O(m\log m+(k+m)\log^2 n)$ time. We also obtain other results with trade-off between preprocessing and query. Even for the special case where $k=1$, our results are better than the previously best method (in PODS 2012), which requires $O(n\log^2 n)$ preprocessing time, $O(n\log^2 n)$ space, and $O(m^2\log^3 n)$ query time. In addition, for the one-dimensional version of this problem, our approach can build an $O(n)$-size data structure in $O(n\log n)$ time that can support $O(\min\{k,\log m\}\cdot m+k+\log n)$ time queries. Further, we extend our techniques to the top-$k$ aggregate farthest neighbor queries, with the same bounds.

preprint2014arXiv

Two-Point $L_1$ Shortest Path Queries in the Plane

Let $\mathcal{P}$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can quickly compute an $L_1$ shortest obstacle-avoiding path between any two query points $s$ and $t$. Previously, a data structure of size $O(n^2\log n)$ was constructed in $O(n^2\log^2 n)$ time that answers each two-point query in $O(\log^2 n+k)$ time, i.e., the shortest path length is reported in $O(\log^2 n)$ time and an actual path is reported in additional $O(k)$ time, where $k$ is the number of edges of the output path. In this paper, we build a new data structure of size $O(n+h^2\cdot \log h \cdot 4^{\sqrt{\log h}})$ in $O(n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}})$ time that answers each query in $O(\log n+k)$ time. Note that $n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}}=O(n+h^{2+ε})$ for any constant $ε>0$. Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of $\mathcal{P}$ are rectilinear regions with "weights" and allow $L_1$ paths to travel through them with weighted costs. Our algorithm answers each query in $O(\log n+k)$ time with a data structure of size $O(n^2\cdot \log n\cdot 4^{\sqrt{\log n}})$ that is built in $O(n^2\cdot \log^{2} n\cdot 4^{\sqrt{\log n}})$ time (note that $n^2\cdot \log^{2} n\cdot 4^{\sqrt{\log n}}= O(n^{2+ε})$ for any constant $ε>0$).

preprint2013arXiv

Aggregate-Max Nearest Neighbor Searching in the Plane

We study the aggregate/group nearest neighbor searching for the MAX operator in the plane. For a set $P$ of $n$ points and a query set $Q$ of $m$ points, the query asks for a point of $P$ whose maximum distance to the points in $Q$ is minimized. We present data structures for answering such queries for both $L_1$ and $L_2$ distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the $L_1$ version, we build a data structure of O(n) size in $O(n\log n)$ time, such that each query can be answered in $O(m+\log n)$ time. For the $L_2$ version, we build a data structure in $O(n\log n)$ time and $O(n\log \log n)$ space, such that each query can be answered in $O(m\sqrt{n}\log^{O(1)} n)$ time, and alternatively, we build a data structure in $O(n^{2+ε})$ time and space for any $ε>0$, such that each query can be answered in $O(m\log n)$ time. Further, we extend our result for the $L_1$ version to the top-$k$ queries where each query asks for the $k$ points of $P$ whose maximum distances to $Q$ are the smallest for any $k$ with $1\leq k\leq n$: We build a data structure of O(n) size in $O(n\log n)$ time, such that each top-$k$ query can be answered in $O(m+k\log n)$ time.

preprint2013arXiv

Matroid and Knapsack Center Problems

In the classic $k$-center problem, we are given a metric graph, and the objective is to open $k$ nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of $k$-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: 1. We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version. 2. We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of $1+ε$. We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by $1+ε$.

preprint2012arXiv

Computing L1 Shortest Paths among Polygonal Obstacles in the Plane

Given a point $s$ and a set of $h$ pairwise disjoint polygonal obstacles of totally $n$ vertices in the plane, we present a new algorithm for building an $L_1$ shortest path map of size O(n) in $O(T)$ time and O(n) space such that for any query point $t$, the length of the $L_1$ shortest obstacle-avoiding path from $s$ to $t$ can be reported in $O(\log n)$ time and the actual shortest path can be found in additional time proportional to the number of edges of the path, where $T$ is the time for triangulating the free space. It is currently known that $T=O(n+h\log^{1+ε}h)$ for an arbitrarily small constant $ε>0$. If the triangulation can be done optimally (i.e., $T=O(n+h\log h)$), then our algorithm is optimal. Previously, the best algorithm computes such an $L_1$ shortest path map in $O(n\log n)$ time and O(n) space. Our techniques can be extended to obtain improved results for other related problems, e.g., computing the $L_1$ geodesic Voronoi diagram for a set of point sites in a polygonal domain, finding shortest paths with fixed orientations, finding approximate Euclidean shortest paths, etc.

preprint2012arXiv

Weak Visibility Queries of Line Segments in Simple Polygons

Given a simple polygon P in the plane, we present new algorithms and data structures for computing the weak visibility polygon from any query line segment in P. We build a data structure in O(n) time and O(n) space that can compute the visibility polygon for any query line segment s in O(k log n) time, where k is the size of the visibility polygon of s and n is the number of vertices of P. Alternatively, we build a data structure in O(n^3) time and O(n^3) space that can compute the visibility polygon for any query line segment in O(k + log n) time.

preprint2011arXiv

Optimal Point Movement for Covering Circular Regions

Given $n$ points in a circular region $C$ in the plane, we study the problems of moving the $n$ points to its boundary to form a regular $n$-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. The problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two versions: the decision version and optimization version. For the min-max problem, we present an $O(n\log^2 n)$ time algorithm for the decision version and an $O(n\log^3 n)$ time algorithm for the optimization version. The previously best algorithms for the two problem versions take $O(n^{3.5})$ time and $O(n^{3.5}\log n)$ time, respectively. For the min-sum problem, we show that a special case with all points initially lying on the boundary of the circular region can be solved in $O(n^2)$ time, improving a previous $O(n^4)$ time solution. For the general min-sum problem, we present a 3-approximation $O(n^2)$ time algorithm, improving the previous $(1+π)$-approximation $O(n^2)$ time algorithm. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm can handle each vertex insertion or deletion on the graph in $O(\log^2 n)$ time. This result is interesting in its own right.

preprint2010arXiv

An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles

In this paper, we study the following problem of reconstructing a simple polygon: Given a cyclically ordered vertex sequence of an unknown simple polygon P of n vertices and, for each vertex v of P, the sequence of angles defined by all the visible vertices of v in P, reconstruct the polygon P (up to similarity). An O(n^3 log n) time algorithm has been proposed for this problem. We present an improved algorithm with running time O(n^2), based on new observations on the geometric structures of the problem. Since the input size (i.e., the total number of input visibility angles) is O(n^2) in the worst case, our algorithm is worst-case optimal.

preprint2009arXiv

Perfect Reflection of Chiral Fermions in Gated Graphene Nanoribbons

We describe the results of a theoretical study of transport through gated metallic graphene nanoribbons using a non-equilibrium Green function method. Although analogies with quantum field theory predict perfect transmission of chiral fermions through gated regions in one dimension, we find \emph{perfect reflection} of chiral fermions in armchair ribbons for specific configurations of the gate. This effect should be measurable in narrow graphene constrictions gated by a charged carbon nanotube.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint

Fields this researcher appears in

Source provenance