{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:13:35Z","timestamp":1777547615533,"version":"3.51.4"},"reference-count":42,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,3,28]],"date-time":"2017-03-28T00:00:00Z","timestamp":1490659200000},"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>In the geometric data model for spatio-temporal data, introduced by Chomicki and Revesz [1], spatio-temporal data are modelled as a finite collection of triangles that are transformed by time-dependent affinities of the plane. To facilitate querying and animation of spatio-temporal data, we present a normal form for data in the geometric data model. We propose an algorithm for constructing this normal form via a spatio-temporal triangulation of geometric data objects. This triangulation algorithm generates new geometric data objects that partition the given objects both in space and in time. A particular property of the proposed partition is that it is invariant under time-dependent affine transformations, and hence independent of the particular choice of coordinate system used to describe the spatio-temporal data in. We can show that our algorithm works correctly and has a polynomial time complexity (of reasonably low degree in the number of input triangles and the maximal degree of the polynomial functions that describe the transformation functions). We also discuss several possible applications of this spatio-temporal triangulation. The application of our affine-invariant spatial triangulation method to image indexing and retrieval is discussed and an experimental evaluation is given in the context of bird images.<\/jats:p>","DOI":"10.3390\/ijgi6040100","type":"journal-article","created":{"date-parts":[[2017,3,28]],"date-time":"2017-03-28T10:24:33Z","timestamp":1490696673000},"page":"100","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Affine-Invariant Triangulation of Spatio-Temporal Data with an Application to Image Retrieval"],"prefix":"10.3390","volume":"6","author":[{"given":"Sofie","family":"Haesevoets","sequence":"first","affiliation":[{"name":"Luciad, Gaston Geenslaan 11, 3001 Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5774-0948","authenticated-orcid":false,"given":"Bart","family":"Kuijpers","sequence":"additional","affiliation":[{"name":"UHasselt \u2013 Hasselt University and transnational University Limburg, Databases and Theoretical Computer Science Research Group, Agoralaan, Gebouw D, 3590 Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Z.","family":"Revesz","sequence":"additional","affiliation":[{"name":"Department of Computer Science & 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,28]]},"reference":[{"key":"ref_1","unstructured":"Chomicki, J., and Revesz, P. (1999, January 1\u20132). A geometric framework for specifying spatiotemporal objects. Proceedings of the 6th International Workshop on Temporal Representation and Reasoning, Orlando, FL, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"B\u00f6hlen, M.H., Jensen, C.S., and Scholl, M. (1999). Spatio-Temporal Database Management, International Workshop STDBM 1999, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-48344-6"},{"key":"ref_3","first-page":"96","article-title":"SQLST: A spatio-temporal data model and query language","volume":"Volume 1920","author":"Storey","year":"2000","journal-title":"Proceedings of the 19th International Conference on Conceptual Modeling (ER\u201900)"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1023\/A:1026086723558","article-title":"Classes of spatiotemporal objects and their closure properties","volume":"39","author":"Chomicki","year":"2003","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/333607.333609","article-title":"Chorochronos: A research network for spatiotemporal database systems","volume":"28","author":"Frank","year":"1999","journal-title":"SIGMOD Rec."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Grumbach, S., Rigaux, P., and Segoufin, L. (1998, January 6\u20137). Spatio-temporal data handling with constraints. Proceedings of the 6th International Symposium on Advances in Geographic Information Systems (ACM-GIS\u201998), Washington, DC, USA.","DOI":"10.1145\/288692.288712"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/352958.352963","article-title":"A foundation for representing and querying moving objects","volume":"25","author":"Bohlen","year":"2000","journal-title":"ACM Trans. Databases Syst."},{"key":"ref_8","unstructured":"Kuijpers, B., Paredaens, J., and Van Gucht, D. (2000, January 7\u20139). Towards a theory of movie database queries. Proceedings of the 7th International Workshop on Temporal Representation and Reasoning, Cape Breton, NS, Canada."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Pfoser, D., and Tryfona, N. (1998, January 6\u20137). Requirements, definitions and notations for spatiotemporal application environments. Proceedings of the 6th International Symposium on Advances in Geographic Information Systems (ACM-GIS\u201998), Washington, DC, USA.","DOI":"10.1145\/288692.288715"},{"key":"ref_10","unstructured":"Kuijpers, B., and Haesevoets, S. (2000, January 7\u20139). Closure properties of classes of spatio-temporal objects under boolean set operations. Proceedings of the 7th International Workshop on Temporal Representation and Reasoning, Cape Breton, NS, Canada."},{"key":"ref_11","first-page":"389","article-title":"Partition and conquer","volume":"Volume 1329","author":"Erwig","year":"1997","journal-title":"Proceedings of the 3rd International Conference on Spatial Information Theory"},{"key":"ref_12","unstructured":"Geerts, F., Haesevoets, S., and Kuijpers, B. (2001, January 8\u201310). A theory of spatio-temporal database queries. Proceedings of the 8th International Workshop Database Programming Languages, DBPL 2001, Frascati, Italy."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1006\/jcss.1999.1630","article-title":"Complete geometric query languages","volume":"58","author":"Gyssens","year":"1999","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Paredaens, J., Van den Bussche, J., and Van Gucht, D. (1994, January 24\u201326). Towards a theory of spatial database queries. Proceedings of the 13th ACM Symposium on Principles of Database Systems, Minneapolis, MN, USA.","DOI":"10.1145\/182591.182640"},{"key":"ref_15","unstructured":"Tippet, J. (1965). Optical and Electro-Optical Information Processing, Massachusetts Institute of Technology Press."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1023\/A:1008022116857","article-title":"Reliable and efficient pattern matching using an affine invariant metric","volume":"31","author":"Hagedoorn","year":"1999","journal-title":"Int. J. Comput. Vis."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1109\/34.232073","article-title":"Comparing images using the Hausdorff distance","volume":"15","author":"Huttenlocher","year":"1998","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_18","first-page":"578","article-title":"Affine-invariant model-based object recognition","volume":"6","author":"Lamdan","year":"1990","journal-title":"Affine-Invariant Model-Based Object Recogn."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-7091-6916-2_13","article-title":"A characterization of an affine invariant triangulation","volume":"Volume 8","author":"Farin","year":"1993","journal-title":"Geometric Modelling, Computing Supplementum"},{"key":"ref_20","unstructured":"Paredaens, J., Kuper, G., and Libkin, L. (2000). Constraint Databases, Springer."},{"key":"ref_21","unstructured":"Revesz, P. (2002). Introduction to Constraint Databases, Springer."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.cag.2016.07.008","article-title":"Estimating affine-invariant structures on triangle meshes","volume":"60","author":"Vieira","year":"2016","journal-title":"Comput. Graph."},{"key":"ref_23","first-page":"82","article-title":"A Feature Matching Algorithm Based on an Illumination and Affine Invariant for Aerial Image Registration","volume":"163","author":"Liu","year":"2014","journal-title":"Sens. Transducers"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/j.ijleo.2013.07.008","article-title":"Image matching based local Delaunay triangulation and affine invariant geometric constraint","volume":"125","author":"Dou","year":"2014","journal-title":"Optik"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/s10851-012-0358-7","article-title":"Extensions of Invariant Signatures for Object Recognition","volume":"45","author":"Hoff","year":"2013","journal-title":"J. Math. Imaging Vis."},{"key":"ref_26","first-page":"134","article-title":"Quantifier elimination for real closed fields by cylindrical algebraic decomposition","volume":"Volume 33","author":"Brakhage","year":"1975","journal-title":"Automata Theory and Formal Languages"},{"key":"ref_27","unstructured":"Sarfraz, M., and Banissi, E. (2007, January 4\u20136). Efficient Affine-Invariant Similarity Retrieval. Proceedings of the 2nd International Conference Geometric Modelling and Imaging (GMAI\u201907), Zurich, Switzerland."},{"key":"ref_28","unstructured":"Bochnak, J., Coste, M., and Roy, M.F. (1998). Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"De Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications, Springer.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"De Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications, Springer. Chapter 8.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"De Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications, Springer. Chapter 2.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"De Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications, Springer. Chapter 1.","DOI":"10.1007\/978-3-662-04245-8_1"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","article-title":"Optimal point location in a monotone subdivision","volume":"15","author":"Edelsbrunner","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Dumortier, F., Gyssens, M., Vandeurzen, L., and Van Gucht, D. (1997, January 12\u201314). On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases. Proceedings of the 16th ACM Symposium on Principles of Database Systems, Tucson, AZ, USA.","DOI":"10.1145\/263661.263670"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1006\/jcom.1993.1003","article-title":"Some complexity results for zero finding for univariate functions","volume":"9","author":"Novak","year":"1993","journal-title":"J. Complex."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD international conference on Management of data, Boston, MA, USA.","DOI":"10.1145\/602259.602266"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H., Schneider, R., and Seeger, B. (1990, January 23\u201325). The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA.","DOI":"10.1145\/93597.98741"},{"key":"ref_38","unstructured":"Kamel, I., and Faloutsos, C. (1994, January 12\u201315). Hilbert R-tree: An Improved R-tree using Fractals. Proceedings of the 20th International Conference on Very Large Data Bases VLDB\u201994, Santiago de Chile, Chile."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","article-title":"Quad Trees: A Data Structure for Retrieval on Composite Keys","volume":"4","author":"Finkel","year":"1974","journal-title":"Acta Inform."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1109\/TPAMI.1986.4767851","article-title":"A computational approach to edge detection","volume":"8","author":"Canny","year":"1986","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_41","unstructured":"Trucco, E., and Verri, A. (1998). Introductory Techniques for 3-D Computer Vision, Prentice Halli, Inc."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Haesevoets, S., and Kuijpers, B. (2004, January 12\u201314). Time-dependent affine triangulation of spatio-temporal data. Proceedings of the 12th ACM International Workshop on Geographic Information Systems (ACM-GIS\u201904), Washington, DC, USA.","DOI":"10.1145\/1032222.1032233"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/4\/100\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:31:26Z","timestamp":1760207486000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/4\/100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,28]]},"references-count":42,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,4]]}},"alternative-id":["ijgi6040100"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6040100","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,28]]}}}