Information Technology Reference
In-Depth Information
for designing decomposition algorithms, we have to take into consideration not
only the theoretical approximation bound but also the execution time. We feel
that the experimentation will show that the proposed algorithm may succeed in
both the aspects.
As future work, we propose to study the complexity (and to design decom-
position algorithms) for the opd-tr problem restricted to the case of octilinear
polygons without holes, and to design approximate algorithms for the opd-c
problem.
References
1. Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry.
Discrete Comput. Geom. 4 , 551-581 (1989)
2. Cheng, X., Du, D.-Z., Kim, J.-M., Ruan, L.: Optimal rectangular partitions. In:
Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp.
313-327. Springer, New York (2005)
3. Cicerone, S., Cermignani, M.: Fast and simple approach for polygon schemati-
zation. In: Murgante, B., Gervasi, O., Misra, S., Nedjah, N., Rocha, A.M.A.C.,
Taniar, D., Apduhan, B.O. (eds.) ICCSA 2012, Part I. LNCS, vol. 7333, pp. 267-
279. Springer, Heidelberg (2012)
4. Cicerone, S., Orlandi, A., Archambeault, B., Connor, S., Fan, J., Drewniak, J.L.:
Cavities' identification algorithm for power integrity analysis of complex boards.
In: 20th International Zurich Symposium on Electromagnetic Compatibility (EMC-
Zurich 2009), pp. 253-256. IEEE Press (2009)
5. Ding-Zhu, D., Zhang, Y.: On heuristics for minimum length rectilinear partitions.
Algorithmica 5 (1), 111-128 (1990)
6. Durocher, S., Mehrabi, S.: Computing partitions of rectilinear polygons with
minimum stabbing number. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.)
COCOON 2012. LNCS, vol. 7434, pp. 228-239. Springer, Heidelberg (2012)
7. Eppstein, D.: Graph-theoretic solutions to computational geometry problems.
In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 1-16. Springer,
Heidelberg (2010)
8. Ferrari, L.A., Sankar, P.V., Sklansky, J.: Minimal rectangular partitions of digitized
blobs. Comput. Vis. Graph. Image Process. 28 (1), 58-71 (1984)
9. Imai, H., Asano, T.: Ecient algorithms for geometric graph search problems.
SIAM J. Comput. 15 (2), 478-494 (1986)
10. Keil, J.M.: Polygon decomposition (Chap. 5). In: Sack, J.R., Urrutia, J. (eds.)
Handbook on Computational Geometry, pp. 491-518. Elsevier Science, Amsterdam
(2000)
11. Lei, C.T., Techentin, R.W., Gilbert, B.K.: High-frequency characterization of
power/ground plane structures. IEEE Trans. Microw. Theory Tech. 47 , 562-569
(1999)
12. Lingas, A., Soltan, V.: Minimum convex partition of a polygon with holes by cuts
in given directions. Theory Comput. Syst. 31 , 507-538 (1998)
13. Lipski, W.: An O ( n log n ) manhattan path algorithm. Inf. Process Lett. 19 (2),
99-102 (1984)
14. Lipsky, W., Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two dimensional data
organization II. Fundamenta Informaticae 2 , 245-260 (1979)
Search WWH ::




Custom Search