26 citations · 42 across the 10 of their papers we have counts for
15 papers
How to Catch Grid Points
Sariel Har-Peled, Elfarouk Harb, Qizheng He
Given a positive integer , we study the problem of finding a convex polygon of minimum perimeter that encloses exactly points of . We show that an optimal poly…
Counting numbers that are divisible by the product of their digits
Qizheng He, Carlo Sanna
Let be a positive integer. A natural number is said to be a base- Zuckerman number if it is divisible by the product of its base- digits. Let be…
Enclosing Points with Geometric Objects
Timothy M. Chan, Qizheng He, Jie Xue
Let be a set of points in and be a set of geometric objects in , where . We study the problem of computing a…
Improved Algorithms for Integer Complexity
Qizheng He
The integer complexity of a positive integer is defined as the minimum number of 1's needed to represent , using additions, multiplications and parentheses. We presen…
Simple and Faster Algorithms for Knapsack
Qizheng He, Zhean Xu
In this paper, we obtain a number of new simple pseudo-polynomial time algorithms on the well-known knapsack problem, focusing on the running time dependency on the number of items…
Logical Entity Representation in Knowledge-Graphs for Differentiable Rule Learning
Chi Han, Qizheng He, Charles Yu +3
Probabilistic logical rule learning has shown great strength in logical rule mining and knowledge graph completion. It learns logical rules to predict missing edges by reasoning on…
Dynamic Geometric Set Cover, Revisited
Timothy M. Chan, Qizheng He, Subhash Suri +1
Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may b…
More on Change-Making and Related Problems
Timothy M. Chan, Qizheng He
Given a set of integer-valued coin types and a target value , the well-known change-making problem asks for the minimum number of coins that sum to , assuming an unlimite…
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
Timothy M. Chan, Qizheng He
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an…
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Younan Gao, Meng He, Yakov Nekrich
Under the word RAM model, we design three data structures that can be constructed in time over points in an grid. The first data structure is an…
Faster Approximation Algorithms for Geometric Set Cover
Timothy M. Chan, Qizheng He
We improve the running times of -approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering po…
Further Results on Colored Range Searching
Timothy M. Chan, Qizheng He, Yakov Nekrich
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of colored points in three dimensions, we describe randomized data st…
SOT for MOT
Qizheng He, Jianan Wu, Gang Yu +1
In this paper we present a robust tracker to solve the multiple object tracking (MOT) problem, under the framework of tracking-by-detection. As the first contribution, we innovativ…
The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +3
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (…
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li +2
We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al…