**Geometry: **Most of my research in
this area is in probabilistic (computational) geometry with a few results
in standard computational geometry as well.

- Cheng, S.W., Funke, A.S., Golin, M, Kumar, A.P.,
Poon, S.H., Ramos, A.E.A., ``Curve Reconstruction from Noisy Samples,''
*Computational Geometry: Theory and Applications,*(special issue for papers in SCOCG'2003)*2003 ACM Symposium on Computational Geometry (SoCG'2003)* - Golin, M and Na H., ``On the
Average Complexity of 3D-Voronoi Diagrams of Random Points On Convex Polytopes''
*Computational Geometry: Theory and Applications.*2003. 25. 197-231. PDF conference version appeared in*Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG00).*2000. 127-135. - Golin, M and Na H., ``The Probabilistic Complexity of
the Voronoi Diagram of Points on a Polyhedron'', The
*2002 ACM Symposium on Computational Geometry (SoCG'2002).*PDF - Golin, M., Langerman, S. and Steiger, W.,
``The Convex Hull for Random Lines in the Plane,''
*Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2002).*2002. PDF - Golin, M. ``Limit Theorems for Minimum-Weight
Triangulations, Other Euclidean Functionals and Probabilistic Recurrence
Relations,''
*Proceedings of The Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '96)*, January 1996. PDF - Cheng, S.W., Golin, M. and Tsang, J., ``Expected Case
Analysis of Beta Skeletons with Applications to the Heuristic Construction of
Minimum Weight Triangulations,''
*Proceedings of the 7th Canadian Conference on Computational Geometry.*1995 - Golin, M., "A Provably-Fast, Linear-Expected-Time,
Maxima-Finding Algorithm,"
*Algorithmica,*11, pp. 501-524, 1994. - Golin, M., "How Many Maxima Can There Be?,"
*Computational Geometry: Theory and Applications,"*2, pp. 335-353, 1993. PDF - Golin, M., "Maxima in Convex Regions",
*Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'93)*, pp.352-360, 1993. - Golin, M. and Sedgewick, R., ``Analysis of a Simple but
Efficient Convex Hull Algorithm,''
*Proceedings of the Fourth Annual Symposium on Computational Geometry*. 153-163. 1988

- Ahn, H.K., Cheng, S.W., Cheong, O., Golin, M., Oostrum, R.v.,
``Competitive Facility Location along a Highway, ''
*Proceedings of the 7th International Computing and Combinatorics Conference (COCOON'01)*. August 20-23, 2001. - M . Golin, R. Raman, C. Schwarz and M. Smid, ``Randomized
Data Structures for the Dynamic Closest Pair Problem,''
*Siam Journal on Computing*, August, 1998, 27(4), 1036-1072. PS conference version appeared in*Proceedings of the Fourth Annual Symposium on Discrete Algorithms (SODA '93)*. 301-310. 1993 PDF - Devillers, O. and Golin, M., "Dog Bites Postman: Point
Location in the Voronoi Diagram and Related Problems",
*International Journal of Computational Geometry and Applications,*8(3), 321-342, 1998. conference version appeared in*Proceedings of the First Annual European Symposium on Algorithms (ESA '93).* - Devillers, O., Golin, M., Kedem, K., Schirra, S.,
``Queries on Voronoi Diagrams of Moving Points,''
*Computational Geometry: Theory and Applications.*6. 1996. 315-327. conference version appeared in*Proceedings of the 6th Canadian Conference on Computational Geometry.*1994 - Devillers, O. and Golin, M., ``Incremental Algorithms for
the Construction of Convex Hulls of Circles and Lower Envelopes of
Parabolas,''
*Information Processing Letters.*56(3). 1995. 157-164. conference version appeared in*Proceedings of the 6th Canadian Conference on Computational Geometry.*1994. - Golin M., Raman, R., Schwarz, C., Smid, M., ``A Simple
Randomized Closest Pair Algorithm,''
*Nordic Journal on Computing*. 2 1995. 3-27 Preprint (PS) conference version appeared in*Proceedings of the Fifth Canadian Conference on Computational Geometry.*1993 - M . Golin, C.
Schwarz and M. Smid, ``Further Dynamic Computational Geometry,''
*Proceedings of the Fourth Canadian Conference on Computational Geometry*. 154-159. 1992

Tree Structures: Much of my research in this area revolves around prefix codes which can be represented using trees. Some of my early work also dealt with analysis of mergesort (via the analysis of its merge tree).

- Golin, M. Xu, X . and Yu, J. ``A Generic Top-Down Dynamic
Programming Approach to Prefix-Free Codes'',
*The Proceedings of The ACM-SIAM Symposium on Discrete Algorithms (SODA'09) (2009)*PDF - Golin M., and Li, J. ``More Efficient Algorithms and
Analyses for Unequal Letter Cost Prefix-Free Coding'',
*IEEE Transactions on Information Theory*. 54(8) 3412-3424 (Preprint) PDF Conference version appeared in*ISAAC'07*. - Golin M., and Liu, Z., "The
Structure of Optimal Prefix-Free Codes in Restricted Languages:

the Uniform Probability Case (Extended Abstract),"*in Proceedings of the 2005 Workshop on Algorithms and Data Structures (WADS'05). August 2005,*372-384*,*LNCS 3608. PDF (Wads Version) PDF (WADS version + extra diagrams) - Golin, M. and Na, H., ``Generalizing the Kraft-McMillan Inequality to Restricted Languages (Extended Abstract),'' to appear in Proceedings of the 2005 IEEE Data Compression Conference, DCC'2005. March 2005 PDF
- Golin, M. and Ma K.K. ``Algorithms for Infinite
Huffman-Codes,''
*Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'04).*2004 Preprint(PDF) Soda Talk(ps) An expanded version also appears as HKUST TCSC technical report HKUST-TCSC-2004-07. - Golin M, Kenyon,
*34th ACM Symposium on Theory of Computing.*2002 - Bradford, P., Golin, M, Larmore, L., and Rytter, W., ``
Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming
with the Monge Property,''
*Journal of Algorithms.*2002. 42. 277-303. Preprint(ps) conference version appeared in*Sixth European Symposium on Algorithms (ESA'98)*(LNCS 1461). 43-54. 1998 - Siu-Ngan Choi and Golin, M. ``Lopsided Trees I: A
Combinatorial Analysis'',
*Algorithmica.*2001, 31, 240-290. PDF - Golin, M. ``A Combinatorial Approach to Golomb Forests,''
*Theoretical Computer Science.*July 2001, 263(1-2), 283-304 PDF conference version appeared in*International Workshop on Combinatorics and Computer Science (10th Franco-Japanese and 5th Franco-Chinese Conference)*, - Golin, M. and Na, H., ``Optimal prefix-free codes that end
in a specified pattern and similar problems: the uniform probability case,''
*Proceedings of the 2001 IEEE Data Compression Conference, DCC'2001*. March 2001 143-152. PDF - Chan, S-Z., Golin, M, A Dynamic Programming
Algorithm for Constructing Optimal ``1''-ended Binary Prefix-Free Codes'',
*IEEE Transactions on Information Theory.*46 (4). July 2000. 1637-44. PDF conference version appeared in*The 1998 IEEE International Symposium on Information Theory (ISIT98).*45. August 1998. - Golin, M. and Schuster, A. ``Optimal Point-to-Point
Broadcast Algorithms via Lopsided Trees,''
*Discrete Applied Mathematics.*1999, 93, 233-263 conference version appeared in*Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97)*. 63-73.1997. - Golin, M. and Rote, G., ``A Dynamic Programming Algorithm
for Constructing Optimal Prefix-Free Codes for Unequal Letter Costs,"
*IEEE Transactions on Information Theory*, September 1998, 44(5), 1770-1781. PDF conference version appeared in*Proceedings of the 22nd International Colloquium on Automata Languages and Programming (ICALP '95)*. 256-267. July 1995. - Chow, T. and Golin, M., ``Convergence and Construction of
Minimal-Cost Infinite Trees,''
*The 1998 IEEE International Symposium on Information Theory (ISIT98).*227. August 1998. - Golin, M. and Young, N., "Prefix Codes: Equiprobable Words,
Unequal Letter Costs,"
*SIAM Journal on Computing,*25(6), pp. 1281-1292, December 1996. conference version appeared in*Proceedings of the 21st International Colloquim on Automata Languages and Programming (ICALP '94).*Jerusalem, Israel. 605-617. July 1994

- Cheung, Y.K., Flajolet, Philippe, Golin, M and Lee,
C.Y., `` Multidimensional Divide-and-Conquer and Weighted Digital
Sums'',
*Proceedings of ANALCO 2009*PDF - Flajolet,P. and Golin,M., "Mellin Transforms and
Asymptotics: The Mergesort Recurrence,"
*Acta Informatica,*31, pp. 673-696, 1994. Preprint(ps) conference version appeared in ``Exact Asymptotics of Divide-and-Conquer Recurrences,''*Proceedings of the 20th International Colloquim on Automata Languages and Programming (ICALP '93),'*' Lund, Sweden. 137-149. July 1993. - Golin, M. and Sedgewick R., ``Queue-Mergesort,''
*Information Processing Letters,*48, 253-259. 1993. - Golin, M. and Sedgewick, R., ``Exact Analysis of
Mergesort,'' Presented at the
*Fourth SIAM Conference on Discrete Mathematics (*1988)

Other Tree-Structure Related Papers

- Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin,
M. and Munro, I., ``Fun-Sort,'' to appear in
*Discrete Applied Mathematics.*PS conference version appeared in*Proceedings of the 2nd International Conference `FUN with Algorithms' (FUN-01)*May 29-31, 2001 - Vigneron, A., Gao, L, Golin, M., Italiano, G, Li, B., ``An Algorithm for Finding a k-Median in a Directed Tree,'' Information Processing Letters, 2000. 74, 81-88
- Arya, S., Golin, M. and Mehlhorn, K. ``On the Expected
Depth of Random Circuits,''
*Combinatorics, Probability and Computing.*1999, 8, 209-222. PS - M . Golin, and S. Zaks, ``Labelled Trees and Pairs of
Input-Output Permutations in Priority Queues,''
*Theoretical Computer Science,*1998, 205, 99-114. conference version appeared in*Proceedings of the International Workshop on Graph-theoretic Concepts in Computer Science (WG94).*Munich, Germany. 282-291. June 1994.

Combinatorics:** **
One large project on counting structures in circulant graphs and
a small project on calculating the capacity of two (and higher) dimensional codes. There are
also some one-off problems.

- Yong. X.R., Zhang Y.P. and
Golin, M. ``The Number of Spanning Trees in a Class of Double Fixed-step
Loop Networks'',
*Networks*, 52(2) 69-77 (2008) (Preprint) PDF - Golin, M. Yong. X.R., Zhang Y.P.,
``The Asymptotic Number of Spanning Trees in Circulant Graphs,''
*in The Proceedings of the The Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO07)* - Golin M., Leung, Y.C, Wang, Y.J., ``Permanents of
Circulants: a Transfer Matrix Approach'' (long version with appendix),
*in The Proceedings of the The Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO06)*PDF - Yong. X.R., Zhang Y.P. and
Golin M. ``Chebyshev polynomials and spanning tree formulas for circulant
and related graphs,"
*Discrete Mathematics*298 - Golin, M. Leung Y.C., Wang
Y.J. and Yong X.R., ``Counting Structures in Grid-Graphs, Cylinders and Tori
using Transfer Matrices: Survey and New Results.''
*The Proceedings of the The Second Workshop on Analytic Algorithmics and Combinatorics (ANALCO05)*PDF - Golin, M. Leung Y.C. and Wang Y.J., ``Counting Spanning
Trees and Other Structures in
Non-Constant-Jump Circulant Graphs,''
*The Proceedings of ISAAC'04*. 2004, 508-521. PDF - Golin, M. and Leung Y.C., ``Unhooking Circulant
Graphs:A Combinatorial Method for Counting Spanning Trees and Other
Parameters,''
*The Proceedings of WG'04.*296-307. PDF. An expanded version also appears as HKUST TCSC technical report HKUST-TCSC-2004-02 - Golin, M. and Zhang, Y.P. ``Further applications of
Chebyshev polynomials in the derivation of spanning tree formulas for
circulant graphs,''
*Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities (Proceedings of The International Colloquium on Mathematics and Computer Science, Versailles, France, September 16-19, 2002).*541-552. - Golin, M. and Zhang, Y.P., ``The number of spanning trees
in graphs related to circulant graphs,''
*Poster at the 14th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2002)*FPSAC02 - Zhang Y.P., Yong X.R. and Golin, M. ``The Number of
Spanning Trees in Circulant Graphs'',
*Discrete Mathematics,*2000, 223, 337-350. Preprint(PS) The original final version is available at www.springerlink.com at doi:10.1016/S0012-365X(99)00414-8

- Golin, M., Yong, X.R., Zhang, Y.P. and Sheng, L., ``New
Upper and Lower Bounds on the Channel Capacity of Read/Write Isolated
Memory,''
*Discrete Applied Mathematics.*2004 (140) 35-48.*in Proceedings of The 2000 IEEE International Symposium on Information Theory (ISIT2000).*280 - Golin, M. and Leung Y.C. ``Recurrence Relations on Transfer
Matrices Yield Good Lower and Upper Bounds on the Channel Capacity of Some
2-Dimensional Constrained Systems,''
*Poster in the 2003 IEEE Data Compression Conference (DCC2003).*2003. PDF - Yong, X.R. and Golin, M., ``Algebraic and Combinatorial
Properties of the Transfer Matrix of the 2-Dimensional (1, infinity)-Runlength
Limited constraint,''
*Proceedings of The 2002 IEEE International Symposium on Information Theory (ISIT2002)*. 354. 2002. PDF - Yong, X.R. and Golin, M., ``New Techniques for Bounding
the Channel Capacity of Read/Write Isolated Memory,''
*Poster at the 2002 IEEE Data Compression Conference (DCC2002).*482. 2002. PDF

- Ding, C., Golin, M. and Klove, T., ``Meeting the Welch and
Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets, ''
*Designs, Codes and Cryptography.*2003. (30) 73-84. Preprint(PS) - Fung, W.W., Golin M. and Gray, J., ``Protection of
Keys against Modification Attack,''
*Quality and Reliability Engineering International (special issue on Computer Network Security).*May-June 2002, 18, 217-230 conference version appeared in*Proceedings of the 2001 IEEE Symposium on Security and Privacy,*Oakland, California., May 13-16, 2001*.* - M . Golin, and S. Zaks, ``Labelled Trees and Pairs of
Input-Output Permutations in Priority Queues,''
*Theoretical Computer Science,*1998, 205, 99-114. conference version appeared in*Proceedings of the International Workshop on Graph-theoretic Concepts in Computer Science (WG94).*Munich, Germany. 282-291. June 1994.

Assorted: These are smaller problems that I have worked on that don't fit into the above areas.

- Fleischer, R., Golin, M., Lea, C.T.,
Wong, S., ``Finding Optimal Paths in MREP Routing,''
*Information Processing Letters*. 2004 (89) 57-63. PDF conference version appeared as poster in the*2003 Australian Telecommunications, Networks and Applications Conference (ATNAC03)*. - Lea, C.T., Xie, Q., Golin, M, Fleischer, R. "Residual
Energy Routing with Reverse Energy Cost," Proceedings of
*IEEE Globecom 2003*. PDF

- Golin, M., and Zhang, Y., ``The Two-Median Problem
on Manhattan Meshes'',
*Networks.***49**(3) 226-233 (May 2007) PDF - Fleischer, R., Golin, M. and , Zhang Y.,
``Online Maintenance of K-Medians and K-Covers on a Line,''
*Algorithmica***45**(4) 549-567 (2006)*in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04).*2004. PDF - Vigneron, A., Gao, L, Golin, M., Italiano, G, Li, B., ``An
Algorithm for Finding a k-Median in a Directed Tree,''
*Information Processing Letters*, 2000. 74, 81-88 Preprint(PS) - Bo Li, M. Golin, G. Italiano, X. Deng, and A. K. Sohraby `On The
Optimal Placement of Web Proxies in the Internet,''
*IEEE Infocom'99.*PDF - Li, B., Deng, X., Golin, M and Sohraby, A.K., ``Dynamic and
Distributed Web Caching in Active Networks,''
*Asia Pacific Web Conference (APWeb'98)*. 27-30 September. Beijing, China. 1998

- Bar-Noy, A., Feng Y., and Golin, M, ``Paging
Mobile Users Efficiently and Optimally,''
*to appear in Proceedings of the IEEE INFOCOM'07*PDF - Bar-Noy, A., Golin, M. and Zhang, Y. ``Online
Dynamic Programming Speedups, to appear in Theory of Computing Systems
(invited special issue for WAOA'06) papers. (Preprint)
PDF Conference version
appeared in
*WAOA'06* - Bein, W, Golin, M., Larmore, L. and Zhang, Y. `` The
Knuth-Yao Quadrangle Inequality Speedup is a Consequence of Total
Monotonicity,'' (Preprint) PDF To appear in the
*ACM Transactions on Algorithms*. Conference version appeared in*The 2006 ACM-SIAM Symposium on Discrete Algorithms (SODA'06)*. - Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin,
M., King J.A. and Munro, I., ``Fun-Sort--or the Chaos of Unordered
Binary Search,''
*Discrete Applied Mathematics.*2004 (144) 231-236. PDF conference version appeared in*Proceedings of the 2nd International Conference `FUN with Algorithms' (FUN-01)*May 29-31, 2001 - Ding, C., Golin, M. and Klove, T., ``Meeting the Welch and
Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets, ''
*Designs, Codes and Cryptography.*2003. (30) 73-84. Preprint(PS) - Fung, W.W., Golin M. and Gray, J., ``Protection of
Keys against Modification Attack,''
*Quality and Reliability Engineering International (special issue on Computer Network Security).*May-June 2002, 18, 217-230 conference version appeared in*Proceedings of the 2001 IEEE Symposium on Security and Privacy,*Oakland, California., May 13-16, 2001*.* **Ahn, H-K,**Cheng, S.W.**, Choeng, O, Golin, M and Oostrum, R. van, "**Competitive facility location: the Voronoi game,"*Theoretical Computer Science,*(310) 1-3, January 2004, Pages 457-467 Preprint(PDF) conference version appeared in*Proceedings of the 7th International Computing and Combinatorics Conference (COCOON'01)*. August 20-23, 2001.- Arya, S., Golin, M. and Mehlhorn, K. ``On the Expected
Depth of Random Circuits,''
*Combinatorics, Probability and Computing.*1999, 8, 209-222. PS - Golin, M., Supowit, K.J., ``Newton's Method for
Quadratics and Nested Intervals,''
*Complex Systems*. 8. 1994. 161-180

*Return to home page
www.cs.ust.hk/~golin.*

*Last updated
10/08/2009 01:41 PM +0800*