Zhixiang Chen, Bin Fu, Robert Schweller, Boting Yang, Zhiyu Zhao, Binhai Zhu
In this paper, we develop a probabilistic model to approach two scenarios in reality about the singular haplotype reconstruction problem- the incompleteness and inconsistency occurred in the DNA...
On the Inapproximability of the Exemplar Conserved Interval Distance Problem of Genomes (2009)
Zhixiang Chen, Richard H. Fowler, Bin Fu, Binhai Zhu
In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether the...
Zhixiang Chen, Bin Fu, Robert Schweller, Boting Yang, Zhiyu Zhao, Binhai Zhu
In this paper, we develop a probabilistic model to approach two scenarios in reality about the singular haplotype reconstruction problem- the incompleteness and inconsistency occurred in the DNA...
Contour Interpolation with Bounded Dihedral Angles † (2008)
G. Elber, N. Patrikalakis, P. Brunet (editors, Sergey Bereg, Minghui Jiang, Binhai Zhu
In this paper, we present the first nontrivial theoretical bound on the quality of the 3D solids generated by any contour interpolation method. Given two arbitrary parallel contour slices with n...
Protein Local Structure Alignment Under the Discrete Fréchet Distance (2008)
Protein structure alignment is a fundamental problem in computational and structural biology. While there has been lots of experimental/heuristic methods and empirical results, very few results are...
A Simple Probablistic Algorithm for Approximating Two and Three-dimensional Objects 1 (2008)
Approximating complex geometric objects with simple ones is an important problem in geometric computing (i.e. in GIS, graphics, image processing). Usually, given
ABSTRACT Guarding a Terrain by Two Watchtowers ∗ (2008)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases)...
Sergey Bereg, Micha Sharir, Ovidiu Daescu, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain § with ¨ vertices, the two-watchtower problem for § asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie...
Rob Duncan, Jianbo Qian, Antoine Vigneron, Binhai Zhu
In this paper, we present an ¥§¦©¨���������¨� � time solution for the following multi-label map labeling problem: Given a set � of ¨ distinct sites in the plane, place...
On the Planar Two-Watchtower Problem (2007)
Given a polyhedral terrain (mountain landscape), the shortest watchtower problem is to compute the shortest vertical segment uv erected on the terrain such that every point on the surface of the...
A Simple Probablistic Algorithm for Approximating Two and Three-dimensional Objects (2007)
this paper.) Nevertheless, several approximation algorithms have been proposed to solve this problem and among them Mitchell and Suri first proposed an O(n
On Building an Intelligent WWW Search Engine with On-Line Learning Algorithms (2007)
Zhixiang Chen, Xiannong Meng, Binhai Zhu, Richard Fowler
In this paper, we continue our on-line learning approach [5] towards building an intelligent WWW search engine. We establish a connection between on-line learning theory and search engine...
In this paper, we study the classical problem of preprocessing a set of points to answer nearest neighbor queries on a large spatial database, assuming a coarse grained parallel processor is...
On Building an Intelligent WWW Search Engine with On-Line Learning Algorithms (2007)
Zhixiang Chen, Xiannong Meng, Binhai Zhu, Richard Fowler
In this paper, we continue our on-line learning approach [5] towards building an intelligent WWW search engine. We establish a connection between on-line learning theory and search engine...
L. Devroye, E. P. Mücke, Binhai Zhu
Abstract. This short note considers the problem of point location in a Delaunay triangulation of n random points, using no additional preprocessing or storage other than a standard data structure...
Guarding Polyhedral Terrains Prosenjit Bose (2007)
Thomas Shermer, Godfried Toussaint, Binhai Zhu
We prove that b n
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Rob Duncan, Jianbo Qian, Antoine Vigneron, Binhai Zhu
In this paper, we present an O(n 2 log n) time solution for the following multi-label map labeling problem: Given a set S of n distinct sites in the plane, place at each site a triple of uniform...
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Labeling a Rectilinear Map (2007)
Automatic map-making is an important part of GIS. Although after nearly two decades of development automatic technology can make good maps, cartographic knowledge and experience is still important as...
David Avis, Thomas C. Shermer, Jack Snoeyink, Godfried Toussaint, Binhai Zhu
Let K be a convex polytope in R d, let h(x) be the hyperplane consisting of all points with first coordinate equal to x, and let A(x) be the area (or volume, if d? 3) of the section K "...
On the 1-density of Unit Ball Covering (2007)
Motivated by modern applications like image processing and wireless sensor networks, we consider a variation of the famous Kepler Conjecture. Given any infinite set of unit balls covering the whole...
On the Complexity of Protein Local Structure Alignment Under the Discrete Fr\'echet Distance (2007)
We show that given $m$ proteins (or protein backbones, which are modeled as 3D polygonal chains each of length O(n)) the problem of protein local structure alignment under the discrete Fr\'{e}chet...
Voronoi Diagram of Polygonal Chains under the Discrete Fr\'echet Distance (2007)
Bereg, Sergey, Gavrilova, Marina, Zhu, Binhai
Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is...
Protein structure-structure alignment with discrete Fréchet distance (2007)
Minghui Jiang, Ying Xu, Binhai Zhu
Matching two geometric objects in 2D and 3D spaces is a central problem in computer vision, pattern recognition and protein structure prediction. In particular, the problem of aligning two polygonal...
Non-breaking Similarity of Genomes with Gene Repetitions,”, submitted for publication (2007)
Zhixiang Chen, Bin Fu, Jinhui Xu, Boting Yang, Zhiyu Zhao, Binhai Zhu
Abstract. In this paper we define a new similarity measure, the nonbreaking similarity, which is the complement of the famous breakpoint distance between genomes (in general, between any two...
On the inapproximability of the exemplar conserved interval distance problem of genomes (2007)
Zhixiang Chen, Richard H. Fowler, Bin Fu, Binhai Zhu, Z. Chen, R. H. Fowler, ...
Abstract In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Simeon Ntafos, Micha Sharir, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, ...
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Isoperimetric Inequalities and the Width parameters of graphs (2003)
Chandran, L. Sunil, Telikepalli, Kavitha, Subramanian, C. R., Warnow, Tandy, Zhu, Binhai
Isoperimetric Inequalities and Width Parameters of Graphs (2003)
Telikepalli, Kavitha, Chandran, Sunil, Subramanian, C. R., Warnow, Tandy, Zhu, Binhai
Isoperimetric Inequalities and the Width parameters of graphs (2003)
Chandran, L. Sunil, Telikepalli, Kavitha, Subramanian, C. R., Warnow, Tandy, Zhu, Binhai
Features: Real-Time Adaptive Feature and Document Learning for Web Search (2001)
Zhixiang Chen, Xiannong Meng, Richard H. Fowler, Binhai Zhu
In this article we report our research on building FEA-TURES—an intelligent web search engine that is able to perform real-time adaptive feature (i.e., keyword) and document learning. Not only does...
Features: Real-Time Adaptive Feature and Document Learning for Web Search (2001)
Zhixiang Chen, Xiannong Meng, Richard H. Fowler, Binhai Zhu
In this article we report our research on building FEA-TURES---an intelligent web search engine that is able to perform real-time adaptive feature (i.e., keyword) and document learning. Not only does...
New algorithms for two-label point labeling (2000)
Qin, Zhongping, Wolff, Alexander, Xu, Yin-Feng, Zhu, Binhai
Given a label shape L and a set of n points in the plane, the two-label point-labeling problem consists of placing 2n non-intersecting translated copies of L of maximum size such that each point...
Websail: From on-line learning to web search (2000)
In this paper we investigate the applicability of on-line learning algorithms to the real-world problem of web search. Consider that web documents are indexed using Boolean features. We first...
Some formal analysis of the Rocchio's similarity-based relevance feedback algorithm (2000)
Rocchio's similarity-based Relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm...
Some formal analysis of the Rocchio's similarity-based relevance feedback algorithm (2000)
Abstract. Rocchio's similarity-based Relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning...
Zhixiang Chen, Xiannong Meng, Richard H. Fowler, Binhai Zhu
In this paper we report our research on building Features- an intelligent web search engine that is able to perform real-time adaptive feature (i.e., keyword) and document learning. Not only does...
Websail: From on-line learning to web search (2000)
Zhixiang Chen, Xiannong Meng, Binhai Zhu, Richard H. Fowler
In this paper we investigate the applicability of on-line learning algorithms to the real-world problem of web search. Consider that web documents are indexed using n Boolean features. We first...
New Algorithms for Two-Label Point Labeling (2000)
Zhongping Qin, Alexander Wolff, Yinfeng Xu, Binhai Zhu
. Given a label shape L and a set of n points in the plane, the 2-label point-labeling problem consists of placing 2n non-intersecting translated copies of L of maximum size such that each point...
New Algorithms for Two-Label Point Labeling (2000)
Zhongping Qin, Alexander Wolff, Yinfeng Xu, Binhai Zhu
Given a label shape L and a set of n points in the plane, the two-label point-labeling problem consists of placing 2n non-intersecting translated copies of L of maximum size such that each point...
Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback Algorithm (2000)
Rocchio's similarity-based Relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm...
Websail: From on-line learning to web search (2000)
Zhixiang Chen, Xiannong Meng, Binhai Zhu, Richard H. Fowler
In this paper we report our research on building WebSail {anintelligent web search engine that is able to perform real-time adaptive learning. WebSail learns from the user's relevance feedback,...
Some formal analysis of the Rocchio's similarity-based relevance feedback algorithm (2000)
Abstract. Rocchio’s similarity-based Relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning...
In this paper, we develop a probabilistic model to approach two realistic scenarios regarding the singular haplotype reconstruction problem- the incompleteness and inconsistency occurred in the DNA...
Unoriented Theta-Maxima In The Plane: Complexity And Algorithms (1998)
David Avis, Bryan Beresford-smith, Luc Devroye, Hossam Elgindy, Eric Guévremont, Ferran Hurtado, ...
We introduce the unoriented Theta-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented Theta-maximum of a set of...
Citizenship: Canadian US Status: Permanent Resident (1998)
with circles.”
Map Labeling and Its Generalizations (1997)
Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Binhai Zhu
Map labeling is of fundamental importance in cartography and geographical information systems and is one of the areas targeted for research by the ACM Computational Geometry Impact Task Force....
Map Labeling and Its Generalizations (1997)
Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Binhai Zhu
Map labeling is of fundamental importance in cartography and geographical information systems and is one of the areas targeted for research by the ACM Computational Geometry Impact Task Force....
Map Labeling and Its Generalizations (1997)
Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Binhai Zhu
Map labeling is of fundamental importance in cartography and geographical information systems and is one of the areas targeted for research by the ACM Computational Geometry Impact Task Force....
Ernst P. Mücke, Isaac Saias, Binhai Zhu
This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point simply by "walking...
Ernst P. Mücke, Isaac Saias, Binhai Zhu
This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point simply by "walking...
Computational geometry in two and a half dimensions (1994)
In this thesis, we study computational geometry in two and a half dimensions. These so-called polyhedral terrains have many applications in practice: computer graphics, navigation and motion...
Computational geometry in two and a half dimensions (1994)
In this thesis, we study computational geometry in two and a half dimensions. These so-called polyhedral terrains have many applications in practice: computer graphics, navigation and motion...
Feasibility of Design in Stereolithography (1993)
Boudewijn Asberg, Gregoria Blanco, Prosenjit Bose, Jesus Garcia-lopez, Mark Overmars, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Guarding Polyhedral Terrains (1992)
Prosenjit Bose, Thomas Shermer, Godfried Toussaint, Binhai Zhu
We prove that b n 2 c vertex guards are always sufficient and sometimes necessary to guard the surface of an n-vertex polyhedral terrain. We also show that b (4n\Gamma4) 13 c edge guards are...
Efficient motion planning in the presence of parallel ray barriers /--by Binhai Zhu. (1991)
"1991 May."
Tetrahedralization of Simple and Non-Simple Polyhedra
Godfried T. Toussaint, Clark Verbrugge, Caoan Wang, Binhai Zhu
It is known that not all simple polyhedra can be tetrahedralized, i.e., decomposed into a set of tetrahedra without adding new vertices (tetrahedralization). We investigate several classes of simple...