A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding ∗ (2009)
Mordecai Golin, Xiaoming Xu, Jiajin Yu
Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding...
1 More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding (2009)
Abstract—There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known...
Structures for the Dynamic Closest-Pair Problem (2009)
We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in k-dimensional...
General Terms Algorithms (2008)
Siu-wing Cheng, Hong Kong, Stefan Funke, Mordecai Golin, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding (2008)
Golin, Mordecai, Xu, Xiaoming, Yu, Jiajin
Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding...
A Dynamic Programming Approach To Length-Limited Huffman Coding (2008)
The ``state-of-the-art'' in Length Limited Huffman Coding algorithms is the $\Theta(ND)$-time, $\Theta(N)$-space one of Hirschberg and Larmore, where $D\le N$ is the length restriction on the code....
Abstract Competitive Facility Location: The Voronoi Game ⋆ (2008)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin, René Oostrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Multidimensional Divide-and-Conquer and Weighted Digital Sums (Extended Abstract) ∗ (2008)
This paper studies two functions arising separately in the analysis of algorithms. The first function is the solution to the Multidimensional Divide-And-Conquer (MDC) Recurrence that arises when...
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, J. Ian Munro
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems (2007)
Apport De Recherche, Olivier Devillers Et, Olivier Devillers Et, Mordecai Golin, Mordecai Golin, Programme Robotique, ...
In this paper, we discuss twovariations of the two-dimensional posto #ce problem that arise when the post-o#ces are n postmen moving with constant velocities. The #rst variation addresses the...
Finding Optimal Paths in MREP Routing (2007)
Rudolf Fleischer Mordecai, Rudolf Fleischer, Mordecai Golin, Chin-tau Lea, Steven Wong
Maximum Residual Energy Path (MREP) routing has been shown an e#ective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the...
Fun-Sort --- Or the Chaos of Unordered (2007)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n...
Apport De Recherche, Olivier Devillers Et, Olivier Devillers Et, Mordecai Golin, Mordecai Golin, Programme Robotique, ...
The existing O#n log n# algorithms for #nding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The di#culty with developing incremental...
More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding (2007)
There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time...
There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time...
Abstract. There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known...
Cunsheng Ding, Mordecai Golin, Torleiv Klo/ve
Abstract. The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados...
Cunsheng Ding, Mordecai Golin, Torleiv Klve
The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados developed...
Curve Reconstruction from Noisy Samples (2003)
Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Curve Reconstruction from Noisy Samples (2003)
Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Curve Reconstruction from Noisy Samples (2003)
Siu-wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Competitive Facility Location: The Voronoi Game (2003)
Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, Rene Van Oostrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Curve Reconstruction from Noisy Samples (2003)
Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kuma, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Huffman Coding with Unequal Letter Costs (2002)
Golin, Mordecai, Kenyon, Claire, Young, Neal E.
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
Prefix Codes: Equiprobable Words, Unequal Letter Costs (2002)
Golin, Mordecai, Young, Neal E.
Describes a near-linear-time algorithm for a variant of Huffman coding, in which the letters may have non-uniform lengths (as in Morse code), but with the restriction that each word to be encoded has...
Competitive Facility Location along a Highway (2002)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Golin, Mordecai, Oostrum, René Van
The convex hull for random lines in the plane (2002)
Mordecai Golin, Stefan Langerman, William Steiger
Abstract. An arrangement of n lines chosen at random from R 2 has a vertex set whose convex hull has constant (expected) size. 1 Introduction and Summary. Let L = {ℓ1,...,ℓn} be a set of lines in...
Competitive Facility Location along a Highway (2001)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Golin, Mordecai, Van Oostrum, René
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Oostrum. Competitive facility location along a highway (2001)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin, Rend Costrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Oostrum. Competitive facility location along a highway (2001)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin
, and Ren'e van Oostrum 1
Oostrum, R. Van, Ahn, Hee-Kap, Golin, Mordecai
A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray...
Optimal Point-to-Point Broadcast Algorithms via Lopsided Trees (1997)
Mordecai Golin, Assaf Schuster
We consider the broadcasting operation in point-to-point packet-switched parallel and distributed networks of processors. We develop a general technique for the design of optimal broadcast algorithms...
Queries on Voronoi Diagrams of Moving Points (1996)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...
Queries on Voronoi Diagrams of Moving Points (1996)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...
Devillers, Olivier, Golin, Mordecai
The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...
Devillers, Olivier, Golin, Mordecai
The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Devillers, Olivier, Golin, Mordecai
The existing $O(n \log n)$ algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...
Dog bites postman: point location in the moving Voronoi diagram and related problems (1994)
Devillers, Olivier, Golin, Mordecai
Disponible dans les fichiers attachés à ce document
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Devillers, Olivier, Golin, Mordecai
The existing $O(n \log n)$ algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...
Dog bites postman: point location in the moving Voronoi diagram and related problems (1994)
Devillers, Olivier, Golin, Mordecai
Disponible dans les fichiers attachés à ce document
Mellin Transforms and Asymptotics: The Mergesort Recurrence (1994)
Philippe Flajolet, Inria Rocquencourt, Mordecai Golin
. Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide--and--conquer algorithms. This note illustrates the techniques by providing a...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, Klara Kedem, ...
Suppose we are given n moving postmen described by their motion equations p i (t) = s i + v i t; i = 1, ..., n, where s i 2 IR 2 is the position of the i'th postman at time t = 0, and v i 2 IR 2...
Olivier Devillers Et, Olivier Devillers, Mordecai Golin, Mordecai Golin, Projet Prisme
: The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...
Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems (1994)
Olivier Devillers Et, Olivier Devillers, Mordecai Golin, Mordecai Golin, Projet Prisme
In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the...
Fun-Sort --- Or the Chaos of Unordered (1994)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n...
Revenge of the dog: Queries on Voronoi diagrams of moving points (1994)
Apport De Recherche, Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, ...
Suppose we are given n moving postmen described by their motion equations p i #t#=s i + v i t; i =1;:::;n, where s i 2 IR is the position of the i'th postman at time t = 0, and v i 2 IR is his...
Randomized data structures for the dynamic closest-pair problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid
Abstract. We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in...
Randomized Data Structures for the Dynamic Closest-Pair Problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid
We describe a new randomized data structure, the sparse partition, for solving the dynamic closestpair problem. Using this data structure the closest pair of a set of n points in D-dimensional space,...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Newton's method for quadratics and nested intervals (1991)
Golin, Mordecai, Supowit, Kenneth J.
Résdumé disponible dans le fichier PDF
Notes on maxima in non-convex regions extended version (1991)
Résumé disponible dans le fichier PDF
A provably-fast linear-expected-time maxima-finding algorithm (1991)
Résumé disponible dans le fichier PDF
Probabilistic analyses of closest pair algorithms (1991)
Résumé disponible dans le fichier PDF
Newton's method for quadratics and nested intervals (1991)
Golin, Mordecai, Supowit, Kenneth J.
Résdumé disponible dans le fichier PDF
Notes on maxima in non-convex regions extended version (1991)
Résumé disponible dans le fichier PDF
A provably-fast linear-expected-time maxima-finding algorithm (1991)
Résumé disponible dans le fichier PDF
Probabilistic analyses of closest pair algorithms (1991)
Résumé disponible dans le fichier PDF