Search

Your search keyword '"LEE, D. T."' showing total 15 results
Start Over Author "LEE, D. T." Topic computational geometry

Refine your results

more »

more »

15 results on '"LEE, D. T."'

1. Optimal Randomized Algorithm for the Density Selection Problem

Author

Lin, Tien-Ching, Lee, D. T., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dong, Yingfei, editor, Du, Ding-Zhu, editor, and Ibarra, Oscar, editor

Published
2009
Full Text
View/download PDF

2. Randomized Algorithm for the Sum Selection Problem

Author

Lin, Tien-Ching, Lee, D. T., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Deng, Xiaotie, editor, and Du, Ding-Zhu, editor

Published
2005
Full Text
View/download PDF

11. An Efficient Algorithm for Multi-Layer Obstacle-Avoiding Rectilinear Steiner Tree Construction.

Author

Chih-Hung Liu, I-Che Chen, and Lee, D. T.

Subjects
COMPUTATIONAL geometry, INTEGRATED circuits, ALGORITHMS, ROUTING (Computer network management), PERPENDICULAR Gothic style (Architecture), STEINER systems
Abstract

We consider the multi-layer obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem and propose a reduction to transform a multi-layer instance into a 3D instance. Based on the reduction we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. [ABSTRACT FROM AUTHOR]

Published
2012

12. Efficient Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Geometric Reduction.

Author

Liu, Chih-Hung, Lin, Chun-Xun, Chen, I-Che, Lee, D. T., and Wang, Ting-Chi

Subjects
STEINER systems, ROUTING algorithms, TREE codes (Coding theory), COMPUTATIONAL geometry, ALGORITHM research
Abstract

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. [ABSTRACT FROM PUBLISHER]

Published
2014
Full Text
View/download PDF

13. A PTAS for Cutting Out Polygons with Lines

Author

Bereg, Sergey, Daescu, Ovidiu, Jiang, Minghui, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chen, Danny Z., editor, and Lee, D. T., editor

Published
2006
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results