{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:35:57Z","timestamp":1742394957692},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157745"},{"type":"electronic","value":"9783642157752"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_41","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T10:47:32Z","timestamp":1283338052000},"page":"475-486","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Cover of Points by Disks in a Simple Polygon"],"prefix":"10.1007","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gila","family":"Morgenstern","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput.\u00a029, 912\u2013953 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"41_CR2","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite vc-dimension. Discrete Comput. Geom.\u00a014(4), 469\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"41_CR3","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms\u00a01(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"41_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Math.\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"issue":"2","key":"41_CR5","first-page":"101","volume":"9","author":"G. Calinescu","year":"2004","unstructured":"Calinescu, G., Mandoiu, I.I., Wan, P.-J., Zelikovsky, A.: Selecting forwarding neighbors in wireless ad hoc networks. MONET\u00a09(2), 101\u2013111 (2004)","journal-title":"MONET"},{"key":"41_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1007\/978-3-540-77120-3_56","volume-title":"Algorithms and Computation","author":"P. Carmi","year":"2007","unstructured":"Carmi, P., Katz, M.J., Lev-Tov, N.: Covering points by unit disks of fixed location. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 644\u2013655. Springer, Heidelberg (2007)"},{"issue":"3","key":"41_CR7","first-page":"16","volume":"57","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM\u00a057(3), Article 16 (2010)","journal-title":"J. ACM"},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Drysdale III., R.L.: Voronoi diagrams based on convex distance functions. In: SCG 1985: Proc. First Annual Sympos. Comput. Geom., pp. 235\u2013244 (1985)","DOI":"10.1145\/323233.323264"},{"issue":"9","key":"41_CR9","doi-asserted-by":"publisher","first-page":"1412","DOI":"10.1109\/5.163409","volume":"80","author":"Y. Chiang","year":"1992","unstructured":"Chiang, Y., Tamassia, R.: Dynamic algorithms in computational geometry. Proc. IEEE\u00a080(9), 1412\u20131434 (1992)","journal-title":"Proc. IEEE"},{"issue":"3","key":"41_CR10","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/PL00009429","volume":"21","author":"F.Y.L. Chin","year":"1999","unstructured":"Chin, F.Y.L., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom.\u00a021(3), 405\u2013420 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"41_CR11","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput.\u00a01(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"41_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees of a tree are exactly the chordal graphs. J. Combinat. Theory Ser. B\u00a016, 47\u201356 (1974)","journal-title":"J. Combinat. Theory Ser. B"},{"key":"41_CR13","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"41_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume-title":"Topics on Perfect Graphs. Ann. Discrete Math.","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. Ann. Discrete Math., vol.\u00a021, pp. 325\u2013356. North-Holland, Amsterdam (1984)"},{"key":"41_CR15","unstructured":"Halperin, D., Linhart, C.: The minimum enclosing disk with obstacles (1999) (Manuscript)"},{"issue":"1","key":"41_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1006\/jagm.2001.1194","volume":"42","author":"D. Halperin","year":"2002","unstructured":"Halperin, D., Sharir, M., Goldberg, K.Y.: The 2-Center Problem with Obstacles. J. Algorithms\u00a042(1), 109\u2013134 (2002)","journal-title":"J. Algorithms"},{"issue":"1","key":"41_CR17","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"41_CR18","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W.L. Hsu","year":"1991","unstructured":"Hsu, W.L., Tsai, K.H.: Linear time algorithms on circular-arc graphs. Inform. Process. Lett.\u00a040(3), 123\u2013129 (1991)","journal-title":"Inform. Process. Lett."},{"key":"41_CR19","first-page":"17","volume":"15","author":"F. Hurtado","year":"2000","unstructured":"Hurtado, F., Sacrist\u00e1n, V., Toussaint, G.: Some constrained minimax and maximin location problems. Studies in Locational Analysis 15, 17\u201335 (2000)","journal-title":"Studies in Locational Analysis"},{"key":"41_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-642-03367-4_39","volume-title":"11th Int. Sympos. Algorithms and Data Structures (WADS)","author":"M.J. Katz","year":"2009","unstructured":"Katz, M.J., Morgenstern, G.: A scheme for computing minimum covers within simple regions. In: Dehne, F., et al. (eds.) 11th Int. Sympos. Algorithms and Data Structures (WADS). LNCS, vol.\u00a05664, pp. 447\u2013458. Springer, Heidelberg (2009)"},{"key":"41_CR21","unstructured":"Katz, M.J., Morgenstern, G.: Guarding orthogonal art galleries with sliding cameras. In: 25th European Workshop on Comput. Geom, pp. 159\u2013162 (2009)"},{"issue":"3","key":"41_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2007.02.002","volume":"39","author":"M.J. Katz","year":"2008","unstructured":"Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom.\u00a039(3), 219\u2013228 (2008)","journal-title":"Comput. Geom."},{"issue":"1","key":"41_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom.\u00a01(1), 59\u201371 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"41_CR24","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput.\u00a012(1), 28\u201334 (1983)","journal-title":"SIAM J. Comput."},{"key":"41_CR25","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D. Leven","year":"1987","unstructured":"Leven, D., Sharir, M.: Planning a purely translational motion for a convex object in two\u2013dimensional space using generalized Voronoi diagrams. Discrete Comput. Geom.\u00a02, 9\u201331 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"41_CR26","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica\u00a05(2), 215\u2013241 (1990)","journal-title":"Algorithmica"},{"issue":"3","key":"41_CR27","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/0402033","volume":"2","author":"R. Motwani","year":"1989","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Perfect graphs and orthogonally convex covers. SIAM J. Discrete Math.\u00a02(3), 371\u2013392 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"41_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(90)90017-F","volume":"40","author":"R. Motwani","year":"1990","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Covering orthogonal polygons with star polygons: The perfect graph approach. J. Comput. Syst. Sci.\u00a040(1), 19\u201348 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"41_CR29","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Ray, S.: PTAS for geometric hitting set problems via local search. In: SCG 2009: Proc. 25th Annual Sympos. Comput. Geom, pp. 17\u201322 (2009)","DOI":"10.1145\/1542362.1542367"},{"key":"41_CR30","unstructured":"Narayanappa, S., Vojtechovsk\u00fd, P.: An improved approximation factor for the unit disk covering problem. In: 18th Canadian Conf. on Comput. Geom, pp. 15\u201318 (2006)"},{"key":"41_CR31","volume-title":"Davenport-Schinzel Sequences and their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, New York (1995)"},{"issue":"2","key":"41_CR32","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"C. Worman","year":"2007","unstructured":"Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geometry Appl.\u00a017(2), 105\u2013138 (2007)","journal-title":"Int. J. Comput. Geometry Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T16:11:27Z","timestamp":1553011887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}