✦ LIBER ✦

Polynomial time algorithms for three-label point labeling

✍ Scribed by Rob Duncan; Jianbo Qian; Antoine Vigneron; Binhai Zhu

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 155 KB
Volume: 296
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00433-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundaries of its three labeling squares. We also study the problem under the discrete model, i.e., a site must be at the corners of its three label squares. We obtain an optimal (n log n) time algorithm for the latter problem.

📜 SIMILAR VOLUMES

Three new algorithms for multivariate po

Three new algorithms for multivariate polynomial GCD

✍ Tateaki Sasaki; Masayuki Suzuki 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 885 KB

Three new algorithms for multivariate polynomial GCD (greatest common divisor) are given. The first is to calculate a GrSbner basis with a certain term ordering. The second is to calculate the subresultant by treating the coefficients w.r.t, the main variable as truncated power series. The third is

Genetic algorithms for ambiguous labelli

Genetic algorithms for ambiguous labelling problems

✍ Richard Myers; Edwin R. Hancock 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 684 KB

Consistent labelling problems frequently have more than one solution. Most work in the "eld has aimed at disambiguating early in the interpretation process, using only local evidence. This paper starts with a review of the literature on labelling problems and ambiguity. Based on this review, we prop

Polynomial Time Algorithms for Determini

Polynomial Time Algorithms for Determining Optimal Strategies

✍ Dmitrii Lozovanu; Stefan Pickl 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 247 KB

On a relaxation-labeling algorithm for r

On a relaxation-labeling algorithm for real-time contour-based image similarity retrieval

✍ Paul W.H. Kwan; Keisuke Kameyama; Kazuo Toraichi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 186 KB

In this paper, we propose a relaxation-labeling algorithm for real-time contour-based image similarity retrieval that treats the matching between two images as a consistent labeling problem. To satisfy real-time response, our algorithm works by reducing the size of the labeling problem, thus decreas

Tree counting polynomials for labelled g

Tree counting polynomials for labelled graphs part I: Properties

✍ Samuel D. Bedrosian 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 753 KB

The properties of special pairs of tree counting polynomials that relate to a class of incomplete graphs and their complements are presented. These polynomial pairs are related by the previously defined binary complementing operation. In contrast with alternative graph representations, they offer th

Algorithms for connected component label

Algorithms for connected component labeling based on quadtrees

✍ Kunio Aizawa; Shojiro Tanaka; Koyo Motomura; Ryosuke Kadowaki 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract An algorithm of linear time complexity is presented to label connected components of a binary image by a quadtree. For a given node, the search for all adjacent nodes is carried out in __O__(1) (i.e., constant time complexity for the worst case) using our formerly presented algorithm in