{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:11:44Z","timestamp":1760242304821,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T00:00:00Z","timestamp":1489536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>A basic question in computational geometry is how to find the relationship between a set of points and a line in a real plane. In this paper, we present multidimensional data structures for N points that allow answering the following queries for any given input line: (1) estimate in     O ( log N )     time the number of points below the line; (2) return in     O ( log N + k )     time the     k \u2264 N     points that are below the line; and (3) return in     O ( log N )     time the point that is closest to the line. We illustrate the utility of this computational question with GIS applications in air defense and traffic control.<\/jats:p>","DOI":"10.3390\/ijgi6030082","type":"journal-article","created":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T11:39:26Z","timestamp":1489577966000},"page":"82","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Dynamic Data Structure to Efficiently Find the Points below a Line and Estimate Their Number"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5774-0948","authenticated-orcid":false,"given":"Bart","family":"Kuijpers","sequence":"first","affiliation":[{"name":"UHasselt\u2013Hasselt University and transnational University Limburg, Databases and Theoretical Computer Science Research Group, Agoralaan, Gebouw D, Diepenbeek 3590, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Revesz","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, University of Nebraska-Lincoln, 256 Avery Hall, 1144 T Street, Lincoln, NE 68588-0115, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,3,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"De Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Pach, J., and Agarwal, P.K. (1995). Combinatorial Geometry, John Wiley and Sons.","DOI":"10.1002\/9781118033203"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Preparata, F.P., and Shamos, M.I. (1985). Computational Geometry: An Introduction, Springer.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Revesz, P.Z. (2010). Introduction to Databases: From Biological to Spatio-Temporal, Springer.","DOI":"10.1007\/978-1-84996-095-3"},{"key":"ref_5","unstructured":"Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann."},{"key":"ref_6","unstructured":"G\u00fcting, R., and Schneider, M. (2005). Moving Objects Databases, Morgan Kaufmann."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Rigaux, P., Scholl, M., and Agn\u00e9s, V. (2002). Introduction to Spatial Databases: Applications to GIS, Morgan Kaufmann.","DOI":"10.1016\/B978-155860588-6\/50003-8"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s10707-008-0050-7","article-title":"Efficient MaxCount and threshold operators of moving objects","volume":"13","author":"Anderson","year":"2009","journal-title":"Geoinformatica"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Choi, Y.J., and Chung, C.W. (2002, January 4\u20136). Selectivity estimation for spatio-temporal queries to moving objects. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, USA.","DOI":"10.1145\/564691.564742"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1016\/j.is.2005.02.002","article-title":"Spatio-temporal join selectivity","volume":"31","author":"Sun","year":"2006","journal-title":"Inf. Syst."},{"key":"ref_11","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Landis","year":"1962","journal-title":"Soviet Math. Doklady"},{"key":"ref_12","unstructured":"Obe, R.O., and Hsu, L.S. (2011). PostGIS in Action, Manning Publishing."},{"key":"ref_13","unstructured":"Kyzirakos, K., Henson, C.A., Perry, M., Varanka, D., Gr\u00fctter, R., Calbimonte, J., Celino, I., Valle, E.D., Dell\u2019Aglio, D., and Kr\u00f6tzsch, M. (2015, January 11\u201312). Developing GeoSPARQL Applications with Oracle Spatial and Graph. Proceedings of the 1st Joint International Workshop on Semantic Sensor Networks and Terra Cognita (SSN-TC 2015) and the 4th International Workshop on Ordering and Reasoning (OrdRing 2015) co-located with the 14th International Semantic Web Conference (ISWC 2015), Bethlehem, PA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Revesz, P., Kanjamala, P., Li, Y., Liu, Y., and Wang, Y. (2000, January 16\u201318). The MLPQ\/GIS constraint database system. Proceedings of the ACM-SIGMOD International Conference on Management of Data, Dallas, TX, USA.","DOI":"10.1145\/342009.336590"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","article-title":"The Power of Geometric Duality","volume":"25","author":"Chazelle","year":"1985","journal-title":"BIT"},{"key":"ref_16","unstructured":"Xiao, N. (2015). GIS Algorithms, SAGE Publishing."},{"key":"ref_17","unstructured":"Revesz, P.Z. (2005, January 23\u201325). Efficient rectangle indexing algorithms based on point dominance. Proceedings of the 12th International Symposium on Temporal Representation and Reasoning, Burlington, VT, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional Binary Search Trees Used for Associative Searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/3\/82\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:30:29Z","timestamp":1760207429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/3\/82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,15]]},"references-count":18,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["ijgi6030082"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6030082","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2017,3,15]]}}}